{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:32:38Z","timestamp":1778293958500,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540542339","type":"print"},{"value":"9783540475163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_172","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:36Z","timestamp":1330209516000},"page":"661-673","source":"Crossref","is-referenced-by-count":12,"title":["Ray shooting in polygons using geodesic triangulations"],"prefix":"10.1007","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herbert","family":"Edelsbrunner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michelangelo","family":"Grigni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"52_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, 315\u2013325.","DOI":"10.1145\/73833.73868"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"B. Chazelle, A theorem on polygon cutting with applications, Proc. 23rd Annu. IEEE Sympos. Foundat. Comput. Sci., (1982), 339\u2013349.","DOI":"10.1109\/SFCS.1982.58"},{"key":"52_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle, Triangulating a simple polygon in linear time, Proc. 31st Annu. IEEE Sympos. Foundat. Comput. Sci., (1990), 220\u2013230. To appear in Discrete Comput. Geom. (1991).","DOI":"10.1109\/FSCS.1990.89541"},{"key":"52_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\u2013181.","journal-title":"Discrete Comput. Geom."},{"key":"52_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\u2013162.","journal-title":"Algorithmica"},{"key":"52_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\u2013191.","journal-title":"Algorithmica"},{"key":"52_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\u2013581.","journal-title":"Discrete Comput. Geom."},{"key":"52_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, Theoretical Computer Science 27 (1983), 241\u2013253.","journal-title":"Theoretical Computer Science"},{"key":"52_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. Computing 15 (1986), 317\u2013340.","journal-title":"SIAM J. Computing"},{"key":"52_CR10","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. Computer Systems Sci. 39 (1989), 126\u2013152.","journal-title":"J. Computer Systems Sci."},{"key":"52_CR11","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\u2013233.","journal-title":"Algorithmica"},{"key":"52_CR12","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. Computing 12 (1983), 28\u201335.","journal-title":"SIAM J. Computing"},{"key":"52_CR13","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. Preparata, Euclidean shortest path in the presence of rectilinear barriers, Networks 14 (1984), 393\u2013410.","journal-title":"Networks"},{"key":"52_CR14","unstructured":"J. Matou\u0161ek, More on cutting arrangements and spanning trees with low stabbing number, Tech. Rept. B-90-2, Freie Universit\u00e4t Berlin, February 1990."},{"key":"52_CR15","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":"52_CR16","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."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_172.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:15:41Z","timestamp":1742591741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_172","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}