{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:15Z","timestamp":1771036335816,"version":"3.50.1"},"reference-count":22,"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\/bf01377183","type":"journal-article","created":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T18:41:34Z","timestamp":1112380894000},"page":"54-68","source":"Crossref","is-referenced-by-count":115,"title":["Ray shooting in polygons using geodesic triangulations"],"prefix":"10.1007","volume":"12","author":[{"given":"B.","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Edelsbrunner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Grigni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"P. 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":"B. Chazelle, A theorem on polygon cutting with applications,Proc. 23rd IEEE Symp. on Foundations of Computer Science, 1982, pp. 339?349.","DOI":"10.1109\/SFCS.1982.58"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle, Triangulating a simple polygon in linear time,Discrete Comput. Geom.,6 (1991), 485?524.","journal-title":"Discrete Comput. Geom."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF02187720","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle, H. Edelsbrunner, and L. Guibas, The complexity of cutting complexes,Discrete Comput. Geom.,4 (1989), 139?181.","journal-title":"Discrete Comput. Geom."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and L. Guibas, Fractional cascading: I. A data structuring technique,Algorithmica,1 (1986), 133?162.","journal-title":"Algorithmica"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF01840441","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and L. Guibas, Fractional cascading: II. Applications,Algorithmica,1 (1986), 163?191.","journal-title":"Algorithmica"},{"key":"CR7","doi-asserted-by":"crossref","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.,4 (1989), 551?581.","journal-title":"Discrete Comput. Geom."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0304-3975(82)90120-7","volume":"27","author":"D. Dobkin","year":"1983","unstructured":"D. Dobkin and D. Kirkpatrick, Fast detection of polyhedral intersection,Theoret. Comput. Sci.,27 (1983), 241?253.","journal-title":"Theoret. Comput. Sci."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput.,15 (1986), 317?340.","journal-title":"SIAM J. Comput."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H. ElGindy","year":"1981","unstructured":"H. ElGindy and D. Avis, A linear algorithm for computing the visibility polygon from a point,J. Algorithms,2 (1981), 186?197.","journal-title":"J. Algorithms"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"L. Guibas","year":"1989","unstructured":"L. Guibas and J. Hershberger, Optimal shortest path queries in a simple polygon,J. Comput. System Sci.,39 (1989), 126?152.","journal-title":"J. Comput. System Sci."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan, Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons,Algorithmica,2 (1987), 209?233.","journal-title":"Algorithmica"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0218195991000025","volume":"1","author":"L. Guibas","year":"1991","unstructured":"L. Guibas, J. Hershberger, and J. Snoeyink, Compact interval trees: a data structure for convex hulls,Internat. J. Comput. Geom. Appl.,1 (1991), 1?22.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. E. Tarjan, Fast algorithms for finding nearest common ancestors,SIAM J. Comput.,13 (1984), 338?355.","journal-title":"SIAM J. Comput."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0020-0190(91)90064-O","volume":"38","author":"J. Hershberger","year":"1991","unstructured":"J. Hershberger, A new data structure for shortest path queries in a simple polygon,Inform. Process. Lett,38 (1991), 231?235.","journal-title":"Inform. Process. Lett"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.,12 (1983), 28?35.","journal-title":"SIAM J. Comput."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers,Networks,14 (1984), 393?410.","journal-title":"Networks"},{"key":"CR18","unstructured":"J. Matou?ek, More on cutting arrangements and spanning trees with low stabbing number, Technical Report B-90-2, Freie Universit\u00e4t Berlin, February 1990."},{"key":"CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms, I: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn,Data Structures and Algorithms, I: Sorting and Searching, Springer-Verlag, Heidelberg, 1984."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J. van Leeuwen, Maintenance of configurations in the plane,J. Comput. System Sci.,23 (1981), 166?204.","journal-title":"J. Comput. System Sci."},{"key":"CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata and M. Shamos,Computational Geometry: An Introduction, Springer-Verlag, Heidelberg, 1985."},{"key":"CR22","series-title":"Lecture Notes in Computer Science, Vol. 319","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BFb0040379","volume-title":"Proc. Third Aegean Workshop on Computing","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization,Proc. Third Aegean Workshop on Computing, pp. 111?123, Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, Berlin, 1988."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01377183.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01377183\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01377183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T05:47:13Z","timestamp":1556862433000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01377183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,7]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,7]]}},"alternative-id":["BF01377183"],"URL":"https:\/\/doi.org\/10.1007\/bf01377183","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,7]]}}}