{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T00:45:37Z","timestamp":1790901937783,"version":"4.1.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1987,11,1]],"date-time":"1987-11-01T00:00:00Z","timestamp":562723200000},"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":[[1987,11]]},"DOI":"10.1007\/bf01840360","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T23:41:00Z","timestamp":1120002060000},"page":"209-233","source":"Crossref","is-referenced-by-count":336,"title":["Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons"],"prefix":"10.1007","volume":"2","author":[{"given":"Leonidas","family":"Guibas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Leven","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01840360_CR1","unstructured":"T. Asano, Efficient algorithms for finding the visibility polygon for a polygonal region with holes, Manuscript, University of California at Berkeley."},{"key":"BF01840360_CR2","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TC.1981.1675729","volume":"30","author":"D. Avis","year":"1981","unstructured":"D. Avis and G. T. Toussaint, An optimal algorithm for determining the visibility of a polygon from an edge,IEEE Trans. Comput.,30 (1981), 910\u2013914.","journal-title":"IEEE Trans. Comput."},{"key":"BF01840360_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle, A theorem on polygon cutting with applications,Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982, pp. 339\u2013349.","DOI":"10.1109\/SFCS.1982.58"},{"key":"BF01840360_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proceedings of the ACM Symposium on Computational Geometry, 1985, pp. 135\u2013146 (also submitted toDiscrete Comput. Geom.).","DOI":"10.1145\/323233.323252"},{"key":"BF01840360_CR5","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stolfi, Optimal point location in monotone subdivisions, Technical Report 2, DEC\/SRC, Palo Alto, CA, 1984."},{"key":"BF01840360_CR6","unstructured":"H. A. El Gindy, An efficient algorithm for computing the weak visibility polygon from an edge in simple polygons, Manuscript, McGill University, 1984."},{"key":"BF01840360_CR7","unstructured":"H. A. El Gindy, Hierarchical decomposition of polygons with applications, Ph.D. Dissertation, School of Computer Science, McGill University, 1985."},{"key":"BF01840360_CR8","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H. A. El Gindy","year":"1981","unstructured":"H. A. El Gindy and D. Avis, A linear algorithm for computing the visibiility polygon from a point,J. Algorithms,2 (1981), 186\u2013197.","journal-title":"J. Algorithms"},{"key":"BF01840360_CR9","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S. Fisk","year":"1978","unstructured":"S. Fisk, A short proof of Chvatal's watchman theorem,J. Combin. Theory Ser. B, 24 (1978), 374.","journal-title":"J. Combin. Theory Ser. B"},{"key":"BF01840360_CR10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics,3 (1984), 153\u2013174.","journal-title":"ACM Trans. Graphics"},{"key":"BF01840360_CR11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Inform. Process. Lett.,7 (1978), 175\u2013179.","journal-title":"Inform. Process. Lett."},{"key":"BF01840360_CR12","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/0196-6774(83)90013-5","volume":"4","author":"R. L. Graham","year":"1983","unstructured":"R. L. Graham and F. F. Yao, Finding the convex hull of a simple polygon,J. Algorithms,4 (1983), 324\u2013331.","journal-title":"J. Algorithms"},{"key":"BF01840360_CR13","unstructured":"D. H. Greene and D. E. Knuth,Mathematics for the Analysis of Algorithms, Birkh\u00e4user, Boston, 1982."},{"key":"BF01840360_CR14","doi-asserted-by":"crossref","unstructured":"L. Guibas, E. McCreight, M. Plass, and J. Roberts, A new representation for linear lists,Proceedings of the Ninth ACM Symposium on Theory of Computing, 1977, pp. 49\u201360.","DOI":"10.1145\/800105.803395"},{"key":"BF01840360_CR15","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic framework for computational geometry,Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, 1983, pp. 100\u2013111.","DOI":"10.1109\/SFCS.1983.1"},{"key":"BF01840360_CR16","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/0020-0190(82)90116-8","volume":"15","author":"P. T. Highman","year":"1982","unstructured":"P. T. Highman, The ears of a polygon,Inform. Process. Lett.,15 (1982), 196\u2013198.","journal-title":"Inform. Process. Lett."},{"key":"BF01840360_CR17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddieston","year":"1982","unstructured":"S. Huddieston and K. Mehlhorn, A new data structure for representing sorted lists,Acta Inform.,17 (1982), 157\u2013184.","journal-title":"Acta Inform."},{"key":"BF01840360_CR18","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\u201335.","journal-title":"SIAM J. Comput."},{"key":"BF01840360_CR19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0734-189X(83)90065-8","volume":"22","author":"D. T. Lee","year":"1983","unstructured":"D. T. Lee, Visibility of a simple polygon,Comput. Vision, Graphics Image Process.,22 (1983) 207\u2013221.","journal-title":"Comput. Vision, Graphics Image Process."},{"key":"BF01840360_CR20","unstructured":"D. T. Lee and A. Lin, Computing the visibility polygon from an edge, Manuscript, Northwestern University, 1984."},{"key":"BF01840360_CR21","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 battiers,Networks,14 (1984), 393\u2013410.","journal-title":"Networks"},{"key":"BF01840360_CR22","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(79)90069-3","volume":"9","author":"D. McCallum","year":"1979","unstructured":"D. McCallum and D. Avis, A linear algorithm for finding the convex hull of a simple polygon,Inform. Process. Lett.,9 (1979), 201\u2013206.","journal-title":"Inform. Process. Lett."},{"key":"BF01840360_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structues and Efficient Algorithms, Vol. I","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn,Data Structues and Efficient Algorithms, Vol. I, Springer-Verlag: Berlin, 1984."},{"key":"BF01840360_CR24","unstructured":"M. A. Peshkin and A. C. Sanderson, Reachable grasps on a polygon: the convex rope algorithm, Technical Report CMU-RI-TR-85-6, Carnegie-Mellon University, 1985. AlsoIEEE J. Robotics Automat. (1986) (to appear)."},{"key":"BF01840360_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"BF01840360_CR26","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0020-0190(81)90091-0","volume":"12","author":"F. P. Preparata","year":"1981","unstructured":"F. P. Preparata and K. J. Supowit, Testing a simple polygon for monotonicity,Inform. Process. Lett.,12 (1981), 161\u2013164.","journal-title":"Inform. Process. Lett."},{"key":"BF01840360_CR27","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach., 32 (1985), 652\u2013686.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01840360_CR28","doi-asserted-by":"crossref","unstructured":"S. Suri, Finding minimum link paths inside a simple polygon,Comput. Vision, Graphics Image Process. (1986) (to appear).","DOI":"10.1016\/0734-189X(86)90070-8"},{"key":"BF01840360_CR29","unstructured":"R. E. Tarjan,Data Structures and Network Algorithme, CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathemataics, Philadelphia, PA, 1983."},{"key":"BF01840360_CR30","unstructured":"R. E. Tarjan and C. Van Wyk, AnO(n log logn) time algorithm for triangulating simple polygons,SIAM J. Comput. (submitted)."},{"key":"BF01840360_CR31","unstructured":"G. Toussaint, Shortest path solves edge-to-edge visibility in a polygon, Technical Report SOCS-85.19, McGill University, 1985."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840360.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840360\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840360","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T21:48:43Z","timestamp":1586296123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,11]]},"references-count":31,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1987,11]]}},"alternative-id":["BF01840360"],"URL":"https:\/\/doi.org\/10.1007\/bf01840360","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,11]]}}}