{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T13:56:44Z","timestamp":1778594204574,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF:AF-1553354"],"award-info":[{"award-number":["CCF:AF-1553354"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1421231"],"award-info":[{"award-number":["CCF-1421231"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217462"],"award-info":[{"award-number":["CCF-1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["824\/17"],"award-info":[{"award-number":["824\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["892\/13"],"award-info":[{"award-number":["892\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1841\/14"],"award-info":[{"award-number":["1841\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2012\/229"],"award-info":[{"award-number":["2012\/229"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific","doi-asserted-by":"publisher","award":["1161\/2011"],"award-info":[{"award-number":["1161\/2011"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00454-019-00141-7","type":"journal-article","created":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T18:02:51Z","timestamp":1576605771000},"page":"109-173","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Decomposing Arrangements of Hyperplanes: VC-Dimension, Combinatorial Dimension, and Point Location"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8133-1335","authenticated-orcid":false,"given":"Esther","family":"Ezra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"issue":"2","key":"141_CR1","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1137\/S009753979426616X","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Schwarzkopf, O.: Computing many faces in arrangements of lines and segments. SIAM J. Comput. 27(2), 491\u2013505 (1998)","journal-title":"SIAM J. Comput."},{"key":"141_CR2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/B978-044482537-7\/50003-6","volume-title":"Handbook of Computational Geometry","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49\u2013119. North-Holland, Amsterdam (2000)"},{"key":"141_CR3","unstructured":"Basu, S.: Algorithms in real algebraic geometry: a survey. In: Monnier, J.-P. (ed.) Real Algebraic Geometry. Panoramas and Synth\u00e8ses, vol. 51, pp. 107\u2013153. Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris (2017). arXiv:1409.1534"},{"key":"141_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"issue":"4","key":"141_CR5","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik\u2013Chervonenkis dimension. J. Assoc. Comput. Mach. 36(4), 929\u2013965 (1989)","journal-title":"J. Assoc. Comput. Mach."},{"key":"141_CR6","volume-title":"Handbook of Data Structures and Applications","author":"B Chazelle","year":"2005","unstructured":"Chazelle, B.: Cuttings. In: Mehta, D.P., Sahni, S. (eds.) Handbook of Data Structures and Applications. Chapman and Hall \/ CRC, Boca Raton (2005)"},{"key":"141_CR7","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: A singly-exponential stratification scheme for real semi-algebraic varieties and its applications. Theoret. Comput. Sci. 84, 77\u2013105 (1991). Also in 16th Int. Colloq. on Automata, Languages and Programming, pp. 179\u2013193 (1989)"},{"issue":"3","key":"141_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229\u2013249 (1990)","journal-title":"Combinatorica"},{"issue":"2","key":"141_CR9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2(2), 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"141_CR10","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"KL Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17(4), 830\u2013847 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"141_CR11","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"KL Clarkson","year":"1993","unstructured":"Clarkson, K.L., Mehlhorn, K., Seidel, R.: Four results on randomized incremental constructions. Comput. Geom. 3(4), 185\u2013212 (1993)","journal-title":"Comput. Geom."},{"issue":"5","key":"141_CR12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"141_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"issue":"4","key":"141_CR14","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S0218195995000210","volume":"5","author":"M de Berg","year":"1995","unstructured":"de Berg, M., Schwarzkopf, O.: Cuttings and applications. Int. J. Comput. Geom. Appl. 5(4), 343\u2013355 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"141_CR15","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1007\/s00454-018-0043-8","volume":"61","author":"E Ezra","year":"2019","unstructured":"Ezra, E., Sharir, M.: A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. Discrete Comput. Geom. 61(4), 735\u2013755 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"141_CR16","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Welzl, E.: Linear programming: randomization and abstract frameworks. In: Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science. Springer Lecture Notes in Computer Science, vol. 1046, pp. 669\u2013687. Springer, Berlin (1996)","DOI":"10.1007\/3-540-60922-9_54"},{"issue":"2","key":"141_CR17","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02570698","volume":"14","author":"LJ Guibas","year":"1995","unstructured":"Guibas, L.J., Halperin, D., Matou\u0161ek, J., Sharir, M.: Vertical decomposition of arrangements of hyperplanes in four dimensions. Discrete Comput. Geom. 14(2), 113\u2013122 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"141_CR18","doi-asserted-by":"crossref","first-page":"2016","DOI":"10.1137\/S0097539799350232","volume":"29","author":"S Har-Peled","year":"2000","unstructured":"Har-Peled, S.: Constructing planar cuttings in theory and practice. SIAM J. Comput. 29(6), 2016\u20132039 (2000)","journal-title":"SIAM J. Comput."},{"key":"141_CR19","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)"},{"issue":"2","key":"141_CR20","first-page":"19","volume":"7","author":"S Har-Peled","year":"2016","unstructured":"Har-Peled, S.: Shortest path in a polygon using sublinear space. J. Comput. Geom. 7(2), 19\u201345 (2016)","journal-title":"J. Comput. Geom."},{"issue":"2","key":"141_CR21","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-Nets and simplex range queries. Discrete Comput. Geom. 2(2), 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"141_CR22","unstructured":"Kane, D.M., Lovett, S., Moran, S.: Generalized comparison trees for point-location problems. In: Chatzigiannakis, C. et al. (eds.) Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs. Leibniz International Proceedings in Informatics, vol. 107, pp. 82:1\u201382:13. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2018)"},{"key":"141_CR23","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Lovett, S., Moran, S.: Near-optimal linear decision trees for k-SUM and related problems. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, (STOC), pp. 554\u2013563. ACM, New York (2018)","DOI":"10.1145\/3188745.3188770"},{"key":"141_CR24","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Lovett, S., Moran, S., Zhang, J.: Active classification with comparison queries. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pp. 355\u2013366. IEEE Computer Society, Los Alamitos (2017)","DOI":"10.1109\/FOCS.2017.40"},{"issue":"3","key":"141_CR25","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s00454-003-2871-3","volume":"31","author":"V Koltun","year":"2004","unstructured":"Koltun, V.: Sharp bounds for vertical decompositions of linear arrangements in four dimensions. Discrete Comput. Geom. 31(3), 435\u2013460 (2004)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"141_CR26","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02187833","volume":"7","author":"J Koml\u00f3s","year":"1992","unstructured":"Koml\u00f3s, J., Pach, J., Woeginger, G.: Almost tight bounds for $$\\varepsilon $$-nets. Discrete Comput. Geom. 7(2), 163\u2013173 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"141_CR27","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.ipl.2004.01.010","volume":"90","author":"D Liu","year":"2004","unstructured":"Liu, D.: A note on point location in arrangements of hyperplanes. Inf. Process. Lett. 90(2), 93\u201395 (2004)","journal-title":"Inf. Process. Lett."},{"key":"141_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)"},{"issue":"2","key":"141_CR29","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1006\/inco.1993.1057","volume":"106","author":"S Meiser","year":"1993","unstructured":"Meiser, S.: Point location in arrangements of hyperplanes. Inf. Comput. 106(2), 286\u2013303 (1993)","journal-title":"Inf. Comput."},{"issue":"3","key":"141_CR30","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F Meyer auf der Heide","year":"1984","unstructured":"Meyer auf der Heide, F.: A polynomial linear search algorithm for the $$n$$-dimensional knapsack problem. J. Assoc. Comput. Mach. 31(3), 668\u2013676 (1984)","journal-title":"J. Assoc. Comput. Mach."},{"key":"141_CR31","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)"},{"key":"141_CR32","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"key":"141_CR33","volume-title":"Algebraic Topology","author":"EH Spanier","year":"1966","unstructured":"Spanier, E.H.: Algebraic Topology. Springer, New York (1966)"},{"key":"141_CR34","doi-asserted-by":"crossref","unstructured":"Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of the frequencies of occurrence of events to their probabilities. In: Empirical Inference, pp. 7\u201312. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-41136-6_2"},{"key":"141_CR35","doi-asserted-by":"crossref","unstructured":"Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","DOI":"10.1137\/1116025"},{"issue":"1","key":"141_CR36","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"HE Warren","year":"1968","unstructured":"Warren, H.E.: Lower bound for approximation by nonlinear manifolds. Trans. Am. Math. Soc. 133(1), 167\u2013178 (1968)","journal-title":"Trans. Am. Math. Soc."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00141-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00141-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00141-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T00:11:47Z","timestamp":1608077507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00141-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,17]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["141"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00141-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,17]]},"assertion":[{"value":"6 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}