{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T18:08:56Z","timestamp":1793124536408,"version":"4.5.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"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":[[1994,4]]},"DOI":"10.1007\/bf02574015","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:08:49Z","timestamp":1174565329000},"page":"393-418","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":91,"title":["On range searching with semialgebraic sets"],"prefix":"10.1007","volume":"11","author":[{"given":"P. K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Matousek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1994,4,1]]},"reference":[{"key":"BF02574015_CR1","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/0221035","volume":"21","author":"P. K. Agarwal","year":"1992","unstructured":"P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number.SIAM J. Comput.\n21 (1992), 540\u2013570.","journal-title":"SIAM J. Comput."},{"key":"BF02574015_CR2","unstructured":"P. K. Agarwal, L. Guibas, M. Pellegrini, and M. Sharir. Ray shooting among spheres. Manuscript, 1993."},{"key":"BF02574015_CR3","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/jagm.1993.1040","volume":"15","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal, M. van Kreveld, and M. Overmars. Intersection queries for curved objects.J. Algorithms\n15 (1993), 229\u2013266.","journal-title":"J. Algorithms"},{"key":"BF02574015_CR4","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal and J. Matou\u0161ek. Ray shooting and parametric search.SIAM J. Comput.\n22 (1993), 794\u2013806.","journal-title":"SIAM J. Comput."},{"key":"BF02574015_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF02189304","volume":"9","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal and M. Sharir. Applications of a new space partitioning scheme.Discrete Comput. Geom.\n9 (1993), 11\u201338.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR6","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, M. Hansen, and T. Leighton. Solving query-retrieval problems by compacting Voronoi diagrams.Proc. 21st ACM Symposium on Theory of Computing, 1990, pp. 331\u2013340. Also to appear inJ. Assoc. Comput. Mach.","DOI":"10.1145\/100216.100260"},{"key":"BF02574015_CR7","doi-asserted-by":"crossref","unstructured":"N. Alon, D. Haussler, E. Welzl, and G. W\u00f6ginger. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension.Proc. 3rd ACM Symposium on Computational Geometry, 1987, pp. 331\u2013340.","DOI":"10.1145\/41958.41994"},{"key":"BF02574015_CR8","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF02189317","volume":"9","author":"B. Aronov","year":"1993","unstructured":"B. Aronov, M. Pellegrini, and M. Sharir. On the zone of a surface in a hyperplane arrangement.Discrete Comput. Geom.\n9 (1993), 177\u2013186.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR9","doi-asserted-by":"crossref","unstructured":"M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal.Proc. 7th Symposium on Computational Geometry, 1991, pp. 51\u201360.","DOI":"10.1145\/109648.109651"},{"key":"BF02574015_CR10","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.J. Amer. Math. Soc.\n2 (1989), 637\u2013666.","journal-title":"J. Amer. Math. Soc."},{"key":"BF02574015_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"B. Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete Comput. Geom.\n9 (1993), 145\u2013158.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(91)90261-Y","volume":"84","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly-exponential stratification scheme for real semi-algebraic varieties and its applications.Theoret. Comput. Sci.\n84 (1991), 77\u2013105. (Also inProc. 16th International Colloquium on Automata, Languages, and Programming, 1989, pp. 179\u2013192).","journal-title":"Theoret. Comput. Sci."},{"key":"BF02574015_CR13","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas M. Sharir, and J. Stolfi. Lines in space: combinatorics and algorithms.Proc. 21st ACM Symposium on Theory of Computing, 1989, pp. 382\u2013393. Also to appear inAlgorithmica.","DOI":"10.1145\/73007.73044"},{"key":"BF02574015_CR14","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\n10 (1990), 229\u2013249.","journal-title":"Combinatorica"},{"key":"BF02574015_CR15","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and L. Guibas. Visibility and intersection problems in plane geometry,Discrete Comput. Geom.\n4 (1989), 551\u2013589.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR16","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems.Algorithmica\n8 (1992), 407\u2013430.","journal-title":"Algorithmica"},{"key":"BF02574015_CR17","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 Comput. Geom.\n4 (1989), 467\u2013490.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR18","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. L. Clarkson","year":"1988","unstructured":"K. L. Clarkson. A randomized algorithm for closest-point queries.SIAM J. Comput.\n17 (1988), 830\u2013847.","journal-title":"SIAM J. Comput."},{"key":"BF02574015_CR19","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. Shor. New applications of random sampling in computational geometry, II.Discrete Comput. Geom.\n4 (1989), 387\u2013421.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR20","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/0196-6774(87)90015-0","volume":"8","author":"D. Dobkin","year":"1987","unstructured":"D. Dobkin and H. Edelsbrunner. Space searching for intersecting objects.J. Algorithms\n8 (1987), 348\u2013361.","journal-title":"J. Algorithms"},{"key":"BF02574015_CR21","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, Berlin, 1987."},{"key":"BF02574015_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl. \u03b5-nets and simplex range queries.Discrete Comput. Geom.\n2 (1987), 127\u2013151.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR23","unstructured":"J. Hershberger and S. Suri. A pedestrian approach to ray shooting: shoot a ray, take a walk.Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 54\u201363."},{"key":"BF02574015_CR24","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF02187833","volume":"7","author":"J. Koml\u00f3s","year":"1992","unstructured":"J. Koml\u00f3s, J. Pach, and G. W\u00f6ginger. Almost tight bounds for epsilon-nets.Discrete Comput. Geom.\n7 (1992), 163\u2013173.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR25","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek. Approximations and optimal geometric divide-and-conquer.Proc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 506\u2013511.","DOI":"10.1145\/103418.103470"},{"key":"BF02574015_CR26","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 Comput. Geom.\n6 (1991), 385\u2013406.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR27","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. Matou\u0161ek. Efficient partition trees.Discrete Comput. Geom.\n8 (1992), 315\u2013334.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR28","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. Matou\u0161ek. Reporting points in half- spaces,Comput. Geom. Theory Appl.\n2 (1992), 169\u2013186.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02574015_CR29","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek. Range searching with efficient hierarchical cuttings.Discrete Comput. Geom.\n10 (1993), 183\u2013196.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574015_CR30","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/BF01187036","volume":"9","author":"M. Pellegrini","year":"1993","unstructured":"M. Pellegrini. Ray shooting in 3-dimensional spaces.Algorithmica\n9 (1993), 471\u2013494.","journal-title":"Algorithmica"},{"key":"BF02574015_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014An Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata and M. I. Shamos.Computational Geometry\u2014An Introduction. Springer-Verlag, New York, 1985."},{"key":"BF02574015_CR32","volume-title":"Analytical Geometry in Three Dimensions","author":"D. Sommerville","year":"1951","unstructured":"D. Sommerville,Analytical Geometry in Three Dimensions. Cambridge University Press, Cambridge, 1951."},{"key":"BF02574015_CR33","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0012-365X(81)90274-0","volume":"33","author":"R. Wenocur","year":"1981","unstructured":"R. Wenocur and R. Dudley. Some Vapnik-Chervonenkis classes.Discrete Math.\n33 (1981), 313\u2013318.","journal-title":"Discrete Math."},{"key":"BF02574015_CR34","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 J. Comput.\n11 (1982), 149\u2013165.","journal-title":"SIAM J. Comput."},{"key":"BF02574015_CR35","doi-asserted-by":"crossref","unstructured":"F. F. Yao and A. C. Yao. A general approach to geometric queries.Proc. 17th ACM Symposium on Theory of Computing, 1985, pp. 163\u2013168.","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\/BF02574015.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02574015\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574015.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,23]],"date-time":"2024-04-23T09:06:56Z","timestamp":1713863216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02574015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["BF02574015"],"URL":"https:\/\/doi.org\/10.1007\/bf02574015","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]},"assertion":[{"value":"13 October 1992","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 1993","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 1994","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"}]}}