{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:09:32Z","timestamp":1787504972060,"version":"build-2736575974"},"reference-count":24,"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\/bf02573975","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T08:07:35Z","timestamp":1174550855000},"page":"215-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":48,"title":["On ray shooting in convex polytopes"],"prefix":"10.1007","volume":"10","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Otfried","family":"Schwarzkopf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1993,8,1]]},"reference":[{"key":"BF02573975_CR1","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"P. K. Agarwal","year":"1991","unstructured":"[AESW] P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs.Discrete & Computational Geometry, 6:407\u2013422, 1991.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573975_CR2","unstructured":"[AM1] P. K. Agarwal and J. Matou\u0161ek. Dynamic half-space range reporting and its applications. Technical Report CS-1991-43, Duke University, 1991."},{"key":"BF02573975_CR3","doi-asserted-by":"crossref","unstructured":"[AM2] P. K. Agarwal and J. Matou\u0161ek. Ray shooting and parametric search. InProc. 24th ACM Symposium on Theory of Computing, pages 517\u2013526, 1992. Full version as Technical Report CS-1991-22, Duke University, 1991.","DOI":"10.1145\/129712.129763"},{"key":"BF02573975_CR4","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. L. Bentley","year":"1980","unstructured":"[BS] J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation.Journal of Algorithms, 1:301\u2013358, 1980.","journal-title":"Journal of Algorithms"},{"key":"BF02573975_CR5","doi-asserted-by":"crossref","unstructured":"[BC] H. Br\u00f6nnimann and B. Chazelle. How hard is halfspace range searching? InProc. 8th Symposium on Computational Geometry, pages 271\u2013275, 1992.","DOI":"10.1145\/142675.142730"},{"key":"BF02573975_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BFb0035760","volume-title":"Proc. 16th International Colloquium on Automata, Languages and Programming","author":"B. Chazelle","year":"1989","unstructured":"[CEGS] B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly-exponential stratification scheme for real semi-algebraic varieties and its applications. InProc. 16th International Colloquium on Automata, Languages and Programming, pages 179\u2013192. Lecture Notes in Computer Science, vol. 372. Springer-Verlag, Berlin, 1989."},{"key":"BF02573975_CR7","unstructured":"[CF] B. Chazelle and J. Friedman. Point location among hyperplanes and vertical ray shooting.Computational Geometry: Theory and Applications (to appear)."},{"key":"BF02573975_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0019-9958(85)80045-0","volume":"64","author":"B. Chazelle","year":"1985","unstructured":"[Ch1] B. Chazelle. How to search in history.Information and Control, 64:77\u201399, 1985.","journal-title":"Information and Control"},{"issue":"4","key":"BF02573975_CR9","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"[Ch2] 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":"BF02573975_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"[Ch3] B. Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete & Computational Geometry, 9:145\u2013158, 1993.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573975_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"[Cl1] K. L. Clarkson. New applications of random sampling in computational geometry.Discrete & Computational Geometry, 2:195\u2013222, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573975_CR12","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. L. Clarkson","year":"1988","unstructured":"[Cl2] K. L. Clarkson. A randomized algorithm for closest-point queries.SIAM Journal on Computing, 17:830\u2013847, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"BF02573975_CR13","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"[CS] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete & Computational Geometry, 4:387\u2013421, 1989.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573975_CR14","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":"BF02573975_CR15","unstructured":"[dBH+] M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal.Algorithmica (to appear)."},{"key":"BF02573975_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"[E] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987."},{"key":"BF02573975_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"[HW] D. Haussler and E. Welzl. \u2208-nets and simplex range queries.Discrete & Computational Geometry, 2:127\u2013151, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573975_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"[Ma1] J. Matou\u0161ek. Efficent partition trees.Discrete & Computational Geometry, 8:315\u2013334, 1992.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02573975_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matou\u0161ek","year":"1992","unstructured":"[Ma2] J. Matou\u0161ek. Reporting points in halfspaces.Computational Geometry: Theory & Applications, 2:169\u2013186, 1992.","journal-title":"Computational Geometry: Theory & Applications"},{"key":"BF02573975_CR20","unstructured":"[Ma3] J. Matou\u0161ek. On vertical ray shooting in arrangements.Computational Geometry: Theory & Applications (to appear)."},{"key":"BF02573975_CR21","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"[Me] N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms.Journal of the ACM, 30:852\u2013865, 1983.","journal-title":"Journal of the ACM"},{"key":"BF02573975_CR22","doi-asserted-by":"crossref","unstructured":"[MS] J. Matou\u0161ek and O. Schwarzkopf. Linear optimization queries. InProc. 8th ACM Symposium on Computational Geometry, pages 16\u201325, 1992.","DOI":"10.1145\/142675.142683"},{"key":"BF02573975_CR23","doi-asserted-by":"crossref","unstructured":"[Mu] K. Mulmuley. Randomized multidimensional search trees: further results in dynamic sampling. InProc. 32nd Symposium on Foundations of Computer Science, pages 216\u2013227, 1991.","DOI":"10.1145\/109648.109662"},{"issue":"5","key":"BF02573975_CR24","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"[S] R. Seidel. Low dimensional linear programming and convex hulls made easy.Discrete & Computational Geometry, 6(5):423\u2013434, 1991.","journal-title":"Discrete & Computational Geometry"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02573975.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02573975\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02573975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02573975.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T23:36:43Z","timestamp":1736897803000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02573975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["BF02573975"],"URL":"https:\/\/doi.org\/10.1007\/bf02573975","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":"6 May 1992","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 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"}]}}