{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T10:50:26Z","timestamp":1756896626493},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1994,7,1]],"date-time":"1994-07-01T00:00:00Z","timestamp":773020800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,7]]},"DOI":"10.1007\/bf01377182","type":"journal-article","created":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T23:41:34Z","timestamp":1112398894000},"page":"30-53","source":"Crossref","is-referenced-by-count":29,"title":["Efficient ray shooting and hidden surface removal"],"prefix":"10.1007","volume":"12","author":[{"given":"M.","family":"de Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Overmars","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"van Kreveld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 315?325.","DOI":"10.1145\/73833.73868"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal and J. Matou?ek, Ray Shooting and Parametric Search,Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 517?526.","DOI":"10.1145\/129712.129763"},{"key":"CR3","first-page":"379","volume-title":"Lecture Notes in Computer Science, Vol. 519","author":"P. K. Agarwal","year":"1991","unstructured":"P. K. Agarwal and M. Sharir, Applications of a New Space Partitioning Technique,Proc. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 379?391."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, M. van Kreveld, and M. Overmars, Intersection Queries for Curved Objects,Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 41?50.","DOI":"10.1145\/109648.109653"},{"key":"CR5","first-page":"13","volume-title":"Lecture Notes in Computer Science, Vol. 519","author":"B. Aronov","year":"1991","unstructured":"B. Aronov and M. Sharir, On the Zone of a Surface in a Hyperplane Arrangement,Proc. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 13?19."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"B. Chazelle, An Optimal Convex Hull Algorithm and New Results on Cuttings,Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 29?38.","DOI":"10.1109\/SFCS.1991.185345"},{"key":"CR7","series-title":"Lecture Notes in Computer Science, Vol. 510","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/3-540-54233-7_172","volume-title":"Proc. 18th Internat. Coll. on Automata, Languages and Programming","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle, H. Edelsbrunner, M. Gringi, L. J. Guibas, M. Sharir, and J. Snoeyink, Ray Shooting in Polygons Using Geodesic Triangulations,Proc. 18th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 510, Springer-Verlag, Berlin, 1991, pp. 661?673."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0925-7721(92)90009-H","volume":"1","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle, H. Edelsbrunner, L. J. Guibas, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, Counting and Cutting Cycles of Lines and Rods in Space,Comput. Geom. Theory Appl. 1 (1992), pp. 305?323.","journal-title":"Comput. Geom. Theory Appl."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir, Lines in Space-Combinatorics, Algorithms and Applications,Proc. 21st ACM Symp. on Theory of Computing, 1989, pp. 382?393.","DOI":"10.1145\/73007.73044"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and L. J. Guibas, Visibility and Intersection Problems in Plane Geometry,Discrete Comput. Geom. 4 (1989), 551?581.","journal-title":"Discrete Comput. Geom."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"B. Chazelle, M. Sharir, and E. Welzl, Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems,Proc. 6th ACM Symp. on Computational Geometry, 1990, pp. 23?33.","DOI":"10.1145\/98524.98532"},{"key":"CR12","unstructured":"S. W. Cheng and R. Janardan, Space-Efficient Ray-Shooting and Intersection Searching: Algorithms, Dynamization and Applications,Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 7?16."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. Clarkson","year":"1987","unstructured":"K. Clarkson, New Applications of Random Sampling in Computational Geometry,Discrete Comput. Geom. 2 (1987), 195?222.","journal-title":"Discrete Comput. Geom."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0747-7171(89)80003-3","volume":"7","author":"R. Cole","year":"1989","unstructured":"R. Cole and M. Sharir, Visibility Problems for Polyhedral Terrains,J. Symbolic Comput. 7 (1989), 11?30.","journal-title":"J. Symbolic Comput."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"M. de Berg and M. H. Overmars, Hidden Surface Removal for Axis-Parallel Polyhedra,Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 252?261.","DOI":"10.1109\/FSCS.1990.89544"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0925-7721(92)90007-F","volume":"1","author":"M. Berg de","year":"1992","unstructured":"M. de Berg and M. H. Overmars, Hidden Surface Removal forc-Oriented Polyhedra,Comput. Geom. Theory Appl. 1 (1992), 247?268.","journal-title":"Comput. Geom. Theory Appl."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. H. Overmars, and O. Schwarzkopf, Computing and Verifying Depth Orders,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 138?145.","DOI":"10.1145\/142675.142708"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/0196-6774(87)90015-0","volume":"8","author":"D. P. Dobkin","year":"1987","unstructured":"D. P. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348?361.","journal-title":"J. Algorithms"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D. P. Dobkin","year":"1985","unstructured":"D. P. Dobkin and D. Kirkpatrick, A Linear Algorithm for Determining the Separation of Convex Polyhedra,J. Algorithms 6 (1985), 381?392.","journal-title":"J. Algorithms"},{"key":"CR20","doi-asserted-by":"crossref","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":"CR21","unstructured":"L. Guibas, M. Overmars, and M. Sharir, Ray Shooting, Implicit Point Location and Related Queries in Arrangements of Segments, Technical Report No. 443, Courant Institute of Mathematical Sciences, New York University, 1989."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl, Epsilon-Nets and Simplex Range Queries,Discrete Comput. Geom. 2 (1987), 127?151.","journal-title":"Discrete Comput. Geom."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick, Optimal Search in Planar Subdivisions,SIAM J. Comput. 12 (1983), 28?35.","journal-title":"SIAM J. Comput."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/27625.27627","volume":"6","author":"M. McKenna","year":"1987","unstructured":"M. McKenna, Worst-Case Optimal Hidden Surface Removal,ACM Trans. Graphics 6 (1987), 19?28.","journal-title":"ACM Trans. Graphics"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF01931656","volume":"30","author":"M. H. Overmars","year":"1990","unstructured":"M. H. Overmars, H. Schipper, and M. Sharir, Storing Line Segments in Partition Trees,BIT 30 (1990), 385?403.","journal-title":"BIT"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"M. H. Overmars and M. Sharir, Output-Sensitive Hidden Surface Removal,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 598?603.","DOI":"10.1109\/SFCS.1989.63541"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"M. Pellegrini, Stabbing and Ray Shooting in 3-Dimensional Space,Proc. 6th ACM Symp. on Computational Geometry, 1990, pp. 177?186.","DOI":"10.1145\/98524.98563"},{"key":"CR28","first-page":"20","volume-title":"Lecture Notes in Computer Science, Vol. 519","author":"M. Pellegrini","year":"1991","unstructured":"M. Pellegrini, New Results on Ray Shooting and Isotopy Classes of Lines in 3-Dimensional Space,Proc. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 20?31."},{"key":"CR29","series-title":"NATO ASI Series, Vol. F40","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1007\/978-3-642-83539-1_42","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"A. Schmitt","year":"1988","unstructured":"A. Schmitt, H. M\u00fcller, and W. Leister, Ray Tracing Algorithms-Theory and Practice, in: R. A. Earnshaw (ed.),Theoretical Foundations of Computer Graphics and CAD, NATO ASI Series, Vol. F40, Springer-Verlag, Berlin, 1988, pp. 997?1030."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"O. Schwarzkopf, Ray Shooting in Convex Polytopes,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 286?295.","DOI":"10.1145\/142675.142734"},{"key":"CR31","unstructured":"J. Stolfi, Primitives for Computational Geometry, Ph.D. Thesis, Computer Science Department, Stanford University, 1988."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01377182.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01377182\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01377182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T16:18:19Z","timestamp":1586189899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01377182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,7]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,7]]}},"alternative-id":["BF01377182"],"URL":"https:\/\/doi.org\/10.1007\/bf01377182","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,7]]}}}