{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T03:55:38Z","timestamp":1752983738295},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1993,5,1]],"date-time":"1993-05-01T00:00:00Z","timestamp":736214400000},"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":[[1993,5]]},"DOI":"10.1007\/bf01187036","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T17:11:10Z","timestamp":1108746670000},"page":"471-494","source":"Crossref","is-referenced-by-count":35,"title":["Ray shooting on triangles in 3-space"],"prefix":"10.1007","volume":"9","author":[{"given":"M.","family":"Pellegrini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"P. K. Agarwal. Partitioning arrangements of lines, I: An efficient deterministic algorithm.Discrete & Computational Geometry, 5:449?483, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"CR2","doi-asserted-by":"crossref","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?573, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"J. Arvo and D. Kirk. Fast ray tracing by ray classification, In M. C. Stone, editor,SIGGRAPH '87 Conference Proceedings, pages 55?63, 1987.","DOI":"10.1145\/37401.37409"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"B. Aronov, J. Matou?ek, and M. Sharir. On the sum of squares of cell complexities in hyperplane arrangements. InProceedings of the 7th ACM Symposium on Computational Geometry, pages 307?313, 1991.","DOI":"10.1145\/109648.109682"},{"key":"CR5","series-title":"Lecture Notes in Computer Science, Volume 519","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BFb0028245","volume-title":"Discrete & Computational Geometry","author":"B. Aronov","year":"1991","unstructured":"B. Aronov, M. Pellegrini, and M. Sharir. On the zone of an algebraic surface in a hyperplane arrangement.Discrete & Computational Geometry. To appear. Preliminary version inProceedings of the 1991 Workshop on Algorithms and Data Structures, pages 13?19. Lecture Notes in Computer Science, Volume 519. Springer-Verlag, Berlin, 1991."},{"key":"CR6","series-title":"Lecture Notes in Computer Science, Volume 519","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BFb0028277","volume-title":"Proceedings of the 1991 Workshop on Algorithms and Data Structures","author":"P. K. Agarwal","year":"1991","unstructured":"P. K. Agarwal and M. Sharir. Applications of a new space partitioning technique. InProceedings of the 1991 Workshop on Algorithms and Data Structures, pages 379?391. Lecture Notes in Computer Science, Volume 519. Springer-Verlag, Berlin, 1991."},{"key":"CR7","unstructured":"M. Bern, D. Dobkin, D. Eppstein, and R. Grossman. Visibility with a moving point. InProceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, pages 107?117, 1990."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"M. Bern. Hidden surface removal for rectangles. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 183?192, 1988.","DOI":"10.1145\/73393.73412"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. InProceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 590?600, 1988.","DOI":"10.1109\/SFCS.1988.21975"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Lines in space: combinatorices, algorithms and applications. InProceedings of the 21st Symposium on Theory of Computing, pages 382?393, 1989.","DOI":"10.1145\/73007.73044"},{"key":"CR11","first-page":"145","volume-title":"Lecture Notes in Computer Sciences, Volume 185","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle.Fast Searching in a Real Algebraic Manifold with Applications to Geometric Complexity, pages 145?156. Lecture Notes in Computer Sciences, Volume 185. Springer-Verlag, Berlin, 1985."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. InProceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 586?591, 1989.","DOI":"10.1109\/SFCS.1989.63539"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"B. Chazelle. An optimal convex hull algorithm and new results on cuttings. InProceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 29?38, 1991.","DOI":"10.1109\/SFCS.1991.185345"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson. New applications of random sampling in computational geometry.Discrete & Computational Geometry, 2:195?222, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"CR15","doi-asserted-by":"crossref","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.SI AM Journal on Computing, 17:830?847, 1988.","journal-title":"SI AM Journal on Computing"},{"key":"CR16","unstructured":"R. Cole and M. Sharir. Visibility Problems for Polyhedral Terrains. Technical Report 266, CIMS, December 1986."},{"key":"CR17","unstructured":"B. Chazelle and M. Sharir. An Algorithm for Generalized Point Location and Its Applications. Technical Report 153, Robotics Laboratory, Courant Institute of Mathematical Sciences, May 1988."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 23?33, 1990.","DOI":"10.1145\/98524.98532"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"M. de Berg, D. Halperlin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficent ray-shooting and hidden surface removal. InProceedings of the 7th ACM Symposium on Computational Geometry, pages 21?30, 1991.","DOI":"10.1145\/109648.109651"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"D. Dobkin and D. Kirkpatrick. Determining the separation of preprocessed polyhedra: a unified approach. InProceedings of the 17th International Colloquium on Automata,Languages and Programming, pages 400?413, 1990.","DOI":"10.1007\/BFb0032047"},{"key":"CR21","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, New York, 1987."},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"[EGS] H. Edelsbrunner, L. Guibas, and M. Sharir. The complexity of many faces in arrangements of lines and segments. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 44?55, 1988.","DOI":"10.1145\/73393.73399"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/BF01934440","volume":"22","author":"H. Edelsbrunner","year":"1982","unstructured":"H. Edelsbrunner, H. Mauer, F. Preparata, E. Welzl, and D. Wood. Stabbing line segments.BIT, 22:274?281, 1982.","journal-title":"BIT"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15:341?363, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"CR25","volume-title":"Ray Tracing","year":"1989","unstructured":"A. S. Glassner, editor.Ray Tracing. Academic Press, New York, 1989."},{"key":"CR26","unstructured":"L. Guibas, M. Overmars, and M. Sharir. Ray Shooting, Implicit Point Location and Related Queries in Arrangements of Segments. Technical Report TR433, Courant Institute, 1989."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/15886.15916","volume":"20","author":"T. L. Kay","year":"1986","unstructured":"T. L. Kay and J. T. Kajiya. Ray tracing complex scenes.Computer Graphics, 20:269?278, 1986.","journal-title":"Computer Graphics"},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"J. Matou?ek. Cutting hyperplane arrangements. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 1?9, 1990.","DOI":"10.1145\/98524.98528"},{"key":"CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-99970-3","volume-title":"Analytic Inequalities","author":"D. S. Mitrinovic","year":"1970","unstructured":"D. S. Mitrinovic.Analytic Inequalities. Springer-Verlag, New York, 1970."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"M. McKenna and J. O'Rourke. Arrangements of lines in 3-space: A data structure with applications. InProceedings of the 4th Annual Symposium on Computational Geometry, pages 371?380, 1988.","DOI":"10.1145\/73393.73431"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(78)90051-8","volume":"7","author":"D. E. Muller","year":"1978","unstructured":"D. E. Muller and F. P. Preparata. Finding the intersection of two convex polyhedra.Theoretical Computer Science, 7:217?236, 1978.","journal-title":"Theoretical Computer Science"},{"key":"CR32","series-title":"Lecture Notes in Computer Science, Volume 199","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1007\/BFb0028837","volume-title":"Proceedings of Fundamentals of Computation Theory","author":"K. Mehlhorn","year":"1985","unstructured":"K., Mehlhorn and K. Simon. Intersecting two polyhedra one of which is convex. InProceedings of Fundamentals of Computation Theory, pages 534?542. Lecture Notes in Computer Science, Volume 199. Springer-Verlag, Berlin, 1985."},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"M. Overmars and M. Sharir, Output-sensitive hidden surface removal. InProceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 598?603, 1989.","DOI":"10.1109\/SFCS.1989.63541"},{"key":"CR34","doi-asserted-by":"crossref","unstructured":"M. H. Overmars and M. Sharir. Merging visibility maps. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 1681?176, 1990.","DOI":"10.1145\/98524.98561"},{"key":"CR35","doi-asserted-by":"crossref","unstructured":"M. Pellegrini. Stabbing and ray shooting in 3-dimensional space. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 177?186, 1990.","DOI":"10.1145\/98524.98563"},{"key":"CR36","unstructured":"M. Pellegrini. Combinatorial and Algorithmic Analysis of Stabbing and Visibility Problems in 3-Dimensional Space. Ph.D. thesis, New York University-Courant Institute of Mathematical Sciences, February 1991. Report Number 241, Robotics Laboratory, Courant Institute."},{"key":"CR37","series-title":"Lecture Notes in Computer Science, Volume 519","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BFb0028246","volume-title":"Proceedings of the1991","author":"M. Pellegrini","year":"1991","unstructured":"M. Pellegrini. Ray shooting and isotopy classes of lines in 3-dimensional space. In Proceedings of the1991, pages 20?31. Lecture Notes in Computer Science, Volume 519. Springer-Verlag, Berlin, 1991."},{"key":"CR38","unstructured":"M. Pellegrini and P. Shor. Finding stabbing lines in 3-dimensional space. InProceedings of the Second SIAM-ACM Symposium on Discrete Algorithms, pages 24?31, 1991."},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"M. S. Paterson and F. F. Yao. Binary partitions with applications to hidden surface removal and solid modelling. InProceedings of the 5th ACM Symposium on Computational Geometry, pages 23?32, 1989.","DOI":"10.1145\/73833.73836"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0146-664X(82)90169-1","volume":"18","author":"S. D. Roth","year":"1982","unstructured":"S. D. Roth. Ray casting for modeling solids.Computer Graphics and Image Processing, 18:109?144, 1982.","journal-title":"Computer Graphics and Image Processing"},{"key":"CR41","doi-asserted-by":"crossref","unstructured":"J. H. Reif and S. Sen. An efficient output-sensitive hidden-surface removal algorithm and its parallelization. InProceedings of the 4th A CM Symposium on Computational Geometry, pages 193?200, 1988.","DOI":"10.1145\/73393.73413"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"R. Seidel. Constructing higher-dimensional convex hulls at logarithmic cost per face. InProceedings of the 18th Annual Symposium on Theory of Computing, pages 404?413,1986.","DOI":"10.1145\/12130.12172"},{"key":"CR43","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0020-0190(88)90120-2","volume":"29","author":"M. Sharir","year":"1988","unstructured":"M. Sharir. The shortest watchtower and related problems for polyhedral terrains.Information Processing Letters, 29:265?270, 1988.","journal-title":"Information Processing Letters"},{"key":"CR44","series-title":"NATO ASI, Volume 40","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. Muller, and W. Leister. Ray tracing algorithms-theory and practice. In R. A. Earnshaw, editor,Theoretical Foundations of Computer Graphics and CAD, pages 997?1030. NATO ASI, Volume 40. Springer-Verlag, New York, 1988."},{"key":"CR45","volume-title":"Analytical geometry of Three Dimensions","author":"D. M. H. Sommerville","year":"1951","unstructured":"D. M. H. Sommerville.Analytical geometry of Three Dimensions. Cambridge University Press, Cambridge, 1951."},{"key":"CR46","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"J. T. Schwartz","year":"1983","unstructured":"J. T. Schwartz and M. Sharir. On the piano mover's problem: II. General techniques for computing topological properties of real algebraic manifolds.Advances in Applied Mathematics, 4:298?35l, 1983.","journal-title":"Advances in Applied Mathematics"},{"key":"CR47","unstructured":"J. Stolfi. Primitives for Computational Geometry. Technical Report 36, Digital SRC, 1989."},{"key":"CR48","volume-title":"CBMS-BSF Regional Conference Series in Applied Mathematics, Volume 44","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan.Data Structures and Newtork Algorithms. CBMS-BSF Regional Conference Series in Applied Mathematics, Volume 44. SIAM, Philadelphia, PA, 1983."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187036.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01187036\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T21:18:00Z","timestamp":1586121480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01187036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,5]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,5]]}},"alternative-id":["BF01187036"],"URL":"https:\/\/doi.org\/10.1007\/bf01187036","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,5]]}}}