{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:26:24Z","timestamp":1725459984587},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584346"},{"type":"electronic","value":"9783540487944"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049414","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T13:42:35Z","timestamp":1141652555000},"page":"266-277","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal shortest path and minimum-link path queries in the presence of obstacles"],"prefix":"10.1007","author":[{"given":"Yi-Jen","family":"Chiang","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Nancy M. Amato. An optimal algorithm for finding the separation of simple polygons. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes in Computer Science, pages 48\u201359. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-57155-8_235"},{"key":"24_CR2","unstructured":"E. M. Arkin, J. S. B. Mitchell, and S. Suri. Optimal link path queries in a simple polygon. In Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms, pages 269\u2013279, 1992."},{"key":"24_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:485\u2013524, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/7531.24036","volume":"34","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle and D. P. Dobkin. Intersection of convex objects in two and three dimensions. J. ACM, 34:1\u201327, 1987.","journal-title":"J. ACM"},{"key":"24_CR5","unstructured":"Y.-J. Chiang, F. P. Preparata, and R. Tamassia. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 44\u201353, 1993."},{"key":"24_CR6","volume-title":"Report CS-94-03","author":"Y.-J. Chiang","year":"1994","unstructured":"Y.-J. Chiang and R. Tamassia. Optimal shortest path and minimum-link path queries between two convex polygons in the presence of obstacles. Report CS-94-03, Comput. Sci. Dept., Brown Univ., Providence, RI, 1994."},{"issue":"12","key":"24_CR7","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1109\/TC.1983.1676186","volume":"C-32","author":"F. Chin","year":"1983","unstructured":"F. Chin and C. A. Wang. Optimal algorithms for the intersection and the minimum distance problems between planar polygons. IEEE Trans. Comput., C-32(12):1203\u20131207, 1983.","journal-title":"IEEE Trans. Comput."},{"key":"24_CR8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"S. Ghosh","year":"1991","unstructured":"S. Ghosh. Computing visibility polygon from a convex set and related problems. J. Algorithms, 12:75\u201395, 1991.","journal-title":"J. Algorithms"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich and R. Tamassia. Dynamic ray shooting and shortest paths via balanced geodesic triangulations. In Proc. 9th Annu. ACM Sympos. Comput. Geom., pages 318\u2013327, 1993.","DOI":"10.1145\/160985.161157"},{"key":"24_CR10","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"L. J. Guibas","year":"1989","unstructured":"L. J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39:126\u2013152, 1989.","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR11","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. H. Overmars","year":"1981","unstructured":"M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23:166\u2013204, 1981.","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"J. H. Reif and J. A. Storer. Minimizing turns for discrete movement in the interior of a polygon. IEEE J. Robot. Autom., pages 182\u2013193, 1987.","DOI":"10.1109\/JRA.1987.1087092"},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/70.88124","volume":"6","author":"S. Suri","year":"1990","unstructured":"S. Suri. On some link distance problems in a simple polygon. IEEE Trans. Robot. Autom., 6:108\u2013113, 1990.","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"3","key":"24_CR15","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421\u2013444, 1987.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049414","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T15:52:32Z","timestamp":1578498752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049414"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0049414","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"23 February 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}