{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:31:49Z","timestamp":1760441509776,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,10,17]],"date-time":"2018-10-17T00:00:00Z","timestamp":1539734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,10,17]],"date-time":"2018-10-17T00:00:00Z","timestamp":1539734400000},"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 (CAREER)"],"award-info":[{"award-number":["CCF:AF 1553354 (CAREER)"]}],"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","892\/13"],"award-info":[{"award-number":["824\/17","892\/13"]}],"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\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hermann Minkowski-MINERVA Center for Geometry"},{"name":"Blavatnik Research Fund"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00454-018-0043-8","type":"journal-article","created":{"date-parts":[[2018,10,17]],"date-time":"2018-10-17T14:16:14Z","timestamp":1539785774000},"page":"735-755","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Nearly Quadratic Bound for Point-Location in Hyperplane Arrangements, in the Linear Decision Tree Model"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8133-1335","authenticated-orcid":false,"given":"Esther","family":"Ezra","sequence":"first","affiliation":[]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,17]]},"reference":[{"key":"43_CR1","first-page":"973","volume-title":"Handbook of Computational Geometry","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 973\u20131027. North-Holland, Amsterdam (2000)"},{"issue":"2","key":"43_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005)","journal-title":"J. ACM"},{"unstructured":"Cardinal, J., Iacono, J., Ooms, A.: Solving $$k$$-SUM using few linear queries. In: Sankowski, P., Zaroliagis, C. (eds.) Proceedings of the 24th European Symposium on Algorithms. LIPIcs. Leibniz International Proceedings in Informatics, vol. 57, pp. 25:1\u201325:17. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2016)","key":"43_CR3"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918), pp. 881\u2013897. SIAM, Philadelphia (2018)","key":"43_CR4","DOI":"10.1137\/1.9781611975031.57"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M., Lewenstein, M.: Clustered integer 3SUM via additive combinatorics. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC\u201915), pp. 31\u201340. ACM, New York (2015)","key":"43_CR5","DOI":"10.1145\/2746539.2746568"},{"issue":"3","key":"43_CR6","doi-asserted-by":"publisher","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"},{"doi-asserted-by":"crossref","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theor. Comput. Sci. 84(1), 77\u2013105 (1991). Also in: Proceedings of the 16th International Colloquium on Automata, Languages and Programming (ICALP\u201989), pp. 179\u2013193 (1989)","key":"43_CR7","DOI":"10.1016\/0304-3975(91)90261-Y"},{"issue":"2","key":"43_CR8","doi-asserted-by":"publisher","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":"5","key":"43_CR9","doi-asserted-by":"publisher","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."},{"issue":"3","key":"43_CR10","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D Dobkin","year":"1978","unstructured":"Dobkin, D., Lipton, R.J.: A lower bound of $$n^2\/2$$ on linear search programs for the knapsack problem. J. Comput. Syst. Sci. 16(3), 413\u2013417 (1978)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"43_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"D Dobkin","year":"1979","unstructured":"Dobkin, D., Lipton, R.J.: On the complexity of computations under varying set of primitives. J. Comput. Syst. Sci. 18(1), 86\u201391 (1979)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 388\u2013395. San Francisco, California (1995)","key":"43_CR12"},{"unstructured":"Ezra, E., Sharir, M.: A nearly quadratic bound for the decision tree complexity of $$k$$-SUM. In: Aronov, B., Katz, M.J. (eds.) Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). Leibniz International Proceedings in Informatics, vol.\u00a077, pp. 41:1\u201341:15. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2017)","key":"43_CR13"},{"unstructured":"Ezra, E., Har-Peled, S., Kaplan, H., Sharir, M.: Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location (2017). \n                    arXiv:1712.02913","key":"43_CR14"},{"issue":"2","key":"43_CR15","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/s00453-015-0079-6","volume":"77","author":"A Freund","year":"2017","unstructured":"Freund, A.: Improved subquadratic 3SUM. Algorithmica 77(2), 440\u2013458 (2017)","journal-title":"Algorithmica"},{"issue":"3","key":"43_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ problems in computational geometry. Comput. Geom. 5(3), 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"unstructured":"Gold, O., Sharir, M.: Improved bounds for 3SUM, $$k$$-SUM, and linear degeneracy. In: Pruhs, K., Sohler, C. (eds.) Proceedings of the 25th European Symposium on Algorithms (ESA\u201917). LIPIcs. Leibniz International Proceedings in Informatics, vol.\u00a087, pp. 42:1\u201342:13. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2017). Also in \n                    arXiv:1512.05279v2","key":"43_CR17"},{"doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201914), pp. 621\u2013630. IEEE, Los Alamitos (2014)","key":"43_CR18","DOI":"10.1109\/FOCS.2014.72"},{"issue":"2","key":"43_CR19","doi-asserted-by":"publisher","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."},{"doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)","key":"43_CR20","DOI":"10.1090\/surv\/173"},{"issue":"2","key":"43_CR21","doi-asserted-by":"publisher","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."},{"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 ACM Symposium on Theory of Computing (STOC\u201915), pp. 554\u2013563. ACM, New York (2018)","key":"43_CR22","DOI":"10.1145\/3188745.3188770"},{"unstructured":"Kane, D.M., Lovett, S., Moran, S.: Generalized comparison trees for point-location problems. In: Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918), vol. 82:1\u201382:13 (2018)","key":"43_CR23"},{"issue":"3","key":"43_CR24","doi-asserted-by":"publisher","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":"43_CR25","doi-asserted-by":"publisher","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."},{"issue":"5","key":"43_CR26","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02574697","volume":"6","author":"J Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Cutting hyperplane arrangements. Discrete Comput. Geom. 6(5), 385\u2013406 (1991)","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)","key":"43_CR27","DOI":"10.1007\/978-1-4613-0039-7"},{"issue":"2","key":"43_CR28","doi-asserted-by":"publisher","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":"43_CR29","doi-asserted-by":"publisher","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. ACM 31(3), 668\u2013676 (1984)","journal-title":"J. ACM"},{"issue":"2","key":"43_CR30","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0097-8493(94)90092-2","volume":"18","author":"D VanArsdale","year":"1994","unstructured":"VanArsdale, D.: Homogeneous transformation matrices for computer graphics. Comput. Graphics 18(2), 177\u2013191 (1994)","journal-title":"Comput. Graphics"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-0043-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-018-0043-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-0043-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:39:29Z","timestamp":1589697569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-018-0043-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,17]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["43"],"URL":"https:\/\/doi.org\/10.1007\/s00454-018-0043-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2018,10,17]]},"assertion":[{"value":"2 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}