{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T22:07:01Z","timestamp":1790460421805,"version":"4.1.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1993,7,1]],"date-time":"1993-07-01T00:00:00Z","timestamp":741484800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1993,7,1]],"date-time":"1993-07-01T00:00:00Z","timestamp":741484800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1993,7]]},"DOI":"10.1007\/bf02573972","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:07:35Z","timestamp":1174565255000},"page":"157-182","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":150,"title":["Range searching with efficient hierarchical cuttings"],"prefix":"10.1007","volume":"10","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1993,8,1]]},"reference":[{"key":"BF02573972_CR1","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"[A] P. K. Agarwal. Partitioning arrangements of lines I: An efficient deterministic algorithm.Discrete & Computational Geometry, 5:449\u2013483, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573972_CR2","series-title":"Lecture notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BFb0028277","volume-title":"Proc. 2nd Workshop on Algorithms and Data Structures","author":"P. K. Agarwal","year":"1991","unstructured":"[AS] P. K. Agarwal and M. Sharir. Applications of a new partitioning scheme. InProc. 2nd Workshop on Algorithms and Data Structures. Lecture notes in Computer Science, vol. 519. Springer-Verlag, Berlin, 1991, pp. 379\u2013391."},{"issue":"4","key":"BF02573972_CR3","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"[C1] B. Chazelle, Lower bounds on the complexity of polytope range searching.Journal of the American Mathematical Society, 2(4):637\u2013666, 1989.","journal-title":"Journal of the American Mathematical Society"},{"key":"BF02573972_CR4","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"[C2] B. Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete & Computational Geometry, 9:145\u2013158, 1993.","journal-title":"Discrete & Computational Geometry"},{"issue":"3","key":"BF02573972_CR5","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"[CF] B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry.Combinatorica, 10(3):229\u2013249, 1990.","journal-title":"Combinatorica"},{"key":"BF02573972_CR6","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"[CSW] B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems.Algorithmica, 8:407\u2013429, 1992.","journal-title":"Algorithmica"},{"key":"BF02573972_CR7","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"[CW] B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension.Discrete & Computational Geometry, 4:467\u2013490, 1989.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573972_CR8","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/0196-6774(87)90015-0","volume":"8","author":"D. Dobkin","year":"1987","unstructured":"[DE] D. Dobkin and H. Edelsbrunner. Space searching for intersecting objects.Journal of Algorithms, 8:348\u2013361, 1987.","journal-title":"Journal of Algorithms"},{"key":"BF02573972_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"[Ed] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987."},{"key":"BF02573972_CR10","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF02187742","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"[EGH+] H. Edelsbrunner, L. Guibas, J. Herschberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl. Implicitly representing arrangements of lines or segments.Discrete & Computational Geometry, 4:433\u2013466, 1989.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573972_CR11","unstructured":"[Ep] D. Eppstein. Private communication, 1992."},{"key":"BF02573972_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(90)90084-B","volume":"36","author":"L. L. Larmore","year":"1990","unstructured":"[L] L. L. Larmore. An optimal algorithm with unknown time complexity for convex matrix searching.Information Processing Letters, 36:147\u2013151, 1990.","journal-title":"Information Processing Letters"},{"key":"BF02573972_CR13","doi-asserted-by":"crossref","unstructured":"[M1] J. Matou\u0161ek. Approximations and optimal geometric divide-and-conquer. InProc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 506\u2013511.","DOI":"10.1145\/103418.103470"},{"issue":"5","key":"BF02573972_CR14","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02574697","volume":"6","author":"J. Matou\u0161ek","year":"1991","unstructured":"[M2] J. Matou\u0161ek. Cutting hyperplane arrangements.Discrete & Computational Geometry, 6(5):385\u2013406, 1991.","journal-title":"Discrete & Computational Geometry"},{"issue":"25","key":"BF02573972_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1051\/ita\/1991250201031","volume":"6","author":"J. Matou\u0161ek","year":"1991","unstructured":"[M3] J. Matou\u0161ek. Spanning trees with low crossing number.Informatique Th\u00e9orique et applications, 6(25):103\u2013123, 1991.","journal-title":"Informatique Th\u00e9orique et applications"},{"key":"BF02573972_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"[M4] J. Matou\u0161ek. Efficeint partition trees.Discrete & Computational Geometry, 8:315\u2013334, 1992.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573972_CR17","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF01931656","volume":"30","author":"M. Overmars","year":"1990","unstructured":"[OSS] M. Overmars, H. Schipper, and M. Sharir. Storing line segments in partition trees.BIT, 30:385\u2013403, 1990.","journal-title":"BIT"},{"key":"BF02573972_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014An Introduction","author":"F. Preparata","year":"1985","unstructured":"[PS] F. Preparata and M. I. Shamos.Computational Geometry\u2014An Introduction. Springer-Verlag, New York, 1985."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02573972.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02573972\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02573972","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02573972.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T07:09:57Z","timestamp":1713424197000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02573972"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["BF02573972"],"URL":"https:\/\/doi.org\/10.1007\/bf02573972","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]},"assertion":[{"value":"1 April 1992","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 1993","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 1993","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}