{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T03:49:01Z","timestamp":1794023341782,"version":"4.8.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1992,8,1]],"date-time":"1992-08-01T00:00:00Z","timestamp":712627200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1992,8,1]],"date-time":"1992-08-01T00:00:00Z","timestamp":712627200000},"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":[[1992,8]]},"DOI":"10.1007\/bf02293051","type":"journal-article","created":{"date-parts":[[2006,2,14]],"date-time":"2006-02-14T07:50:59Z","timestamp":1139903459000},"page":"315-334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":198,"title":["Efficient partition trees"],"prefix":"10.1007","volume":"8","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1992,9,1]]},"reference":[{"key":"BF02293051_CR1","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/BF02187809","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"P. K. Agarwal. Partitioning arrangements of lines, II: Applications.Discrete & Computational Geometry, 5:533\u2013573, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02293051_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, M. Hansen, and T. Leighton. Solving query-retrieval problems by compacting Voronoi diagrams. InProc. 21st ACM Symposium on Theory of Computing, pages 331\u2013340, 1990.","DOI":"10.1145\/100216.100260"},{"key":"BF02293051_CR3","unstructured":"P. K. Agarwal and J. Matou\u0161ek. Dynamic half-space range reporting and its applications. Tech. Report CS-91-43, Duke University, 1991. Extended abstract:Proc. 33rd IEEE Symposium on Foundations of Computer Science, to appear, 1992."},{"key":"BF02293051_CR4","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal and J. Matou\u0161ek. Ray shooting and parametric search. Tech. Report CS-1991-22, Duke University, 1991. Extended abstract:Proc. 24th ACM Symposium on Theory of Computing, 1992.","DOI":"10.1145\/129712.129763"},{"key":"BF02293051_CR5","unstructured":"P. K. Agarwal and M. Sharir. Applications of a new space partitioning scheme. InProc. 2nd Workshop on Algorithms and Data Structures, 1991."},{"key":"BF02293051_CR6","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley. Decomposable searching problems.Information Processing Letters, 8:244\u2013251, 1979.","journal-title":"Information Processing Letters"},{"issue":"3","key":"BF02293051_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"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":"BF02293051_CR8","doi-asserted-by":"crossref","unstructured":"B. Chazelle, L. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25(1), 1985.","DOI":"10.1007\/BF01934990"},{"issue":"4","key":"BF02293051_CR9","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"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":"BF02293051_CR10","unstructured":"B. Chazelle. Cutting hyperplanes for divide-and-conquer. Tech. Report CS-TR-335-91, Princeton University, 1991. Preliminary version:Proc. 32nd IEEE Conference on Foundations of Computer Science, October 1991. To appear inDiscrete & Computational Geometry."},{"key":"BF02293051_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02187685","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and F. P. Preparata. Halfspace range searching: An algorithmic application ofk-sets.Discrete & Computational Geometry, 1:83\u201393, 1986.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02293051_CR12","doi-asserted-by":"crossref","unstructured":"B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. InProc. 6th ACM Symposium on Computational Geometry, pages 23\u201333, 1990.","DOI":"10.1145\/98524.98532"},{"key":"BF02293051_CR13","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"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":"BF02293051_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987"},{"issue":"6","key":"BF02293051_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0020-0190(86)90088-8","volume":"23","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and E. Welzl. Halpflanar range search in linear space andO(n 0.695) query time.Information Processing Letters, 23(6):289\u2013293, 1986.","journal-title":"Information Processing Letters"},{"key":"BF02293051_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl.\u025b-nets and simplex range queries.Discrete & Computational Geometry, 2:127\u2013151, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02293051_CR17","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek. Approximations and optimal geometric divide-and-conquer. InProc. 23rd ACM Symposium on Theory of Computing, pages 506\u2013511, 1991.","DOI":"10.1145\/103418.103470"},{"issue":"5","key":"BF02293051_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02574697","volume":"6","author":"J. Matou\u0161ek","year":"1991","unstructured":"J. Matou\u0161ek. Cutting hyperplane arrangements.Discrete & Computational Geometry, 6(5):385\u2013406, 1991.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02293051_CR19","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek. Range searching with efficient hierarchical cuttings. InProc. 8th ACM Symposium on Computational Geometry, pages 276\u2013285, 1992.","DOI":"10.1145\/142675.142732"},{"key":"BF02293051_CR20","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek. Reporting points in halfspace. inProc. 32nd IEEE Symposium on Foundations of Computer Science, pages 207\u2013215, 1991. Also to appear inComputational Geometry: Theory and Applications.","DOI":"10.1109\/SFCS.1991.185370"},{"key":"BF02293051_CR21","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, E. Welzl, and L. Wernisch. Discrepancy and\u025b-approximations for bounded VC-dimension.Combinatorica, to appear. Also inProc. 32nd IEEE Symposium on Foundations of Computer Science, pages 424\u2013430, 1991.","DOI":"10.1109\/SFCS.1991.185401"},{"key":"BF02293051_CR22","volume-title":"The design of Dynamic Data Structures","author":"M. H. Overmars","year":"1983","unstructured":"M. H. Overmars.The design of Dynamic Data Structures. Springer-Verlag, Berlin, 1983."},{"key":"BF02293051_CR23","series-title":"Lecture Notes in Computer Science","volume-title":"Dynamic partition trees","author":"H. Schipper","year":"1990","unstructured":"H. Schipper and M. H. Overmars. Dynamic partition trees. InProc. 2nd Scandavian Workshop on Algorithms Theory, pages 404\u2013417, 1990. Lecture Notes in Computer Science, Vol. 447. Springer-Verlag, Berlin, 1990. Also to appear inBIT."},{"key":"BF02293051_CR24","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability and its Applications, 16:264\u2013280, 1971.","journal-title":"Theory of Probability and its Applications"},{"key":"BF02293051_CR25","doi-asserted-by":"crossref","unstructured":"E. Welzl. Partition trees for triangle counting and other range searching problems. InProc. 4th ACM Symposium on Computational Geometry, pages 23\u201333, 1988.","DOI":"10.1145\/73393.73397"},{"key":"BF02293051_CR26","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D. E. Willard","year":"1982","unstructured":"D. E. Willard. Polygon retrieval.SIAM Journal on Computing, 11:149\u2013165, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"BF02293051_CR27","doi-asserted-by":"crossref","unstructured":"F. F. Yao and A. C. Yao. A general approach to geometric queries. InProc. 17th ACM Symposium on Theory of Computing, pages 163\u2013168, 1985.","DOI":"10.1145\/22145.22163"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02293051.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02293051\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02293051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02293051.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T13:49:55Z","timestamp":1736257795000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02293051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,8]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,8]]}},"alternative-id":["BF02293051"],"URL":"https:\/\/doi.org\/10.1007\/bf02293051","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,8]]},"assertion":[{"value":"15 April 1991","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 1992","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 1992","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"}]}}