{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T11:30:15Z","timestamp":1768822215731,"version":"3.49.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1989,6,1]],"date-time":"1989-06-01T00:00:00Z","timestamp":612662400000},"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":[[1989,6]]},"DOI":"10.1007\/bf01553883","type":"journal-article","created":{"date-parts":[[2005,4,20]],"date-time":"2005-04-20T22:07:35Z","timestamp":1114034855000},"page":"141-155","source":"Crossref","is-referenced-by-count":61,"title":["An optimal visibility graph algorithm for triangulated simple polygons"],"prefix":"10.1007","volume":"4","author":[{"given":"John","family":"Hershberger","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"No. 1","key":"BF01553883_CR1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T. Asano","year":"1986","unstructured":"T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai: Visibility of disjoint polygons.Algorithmica, Vol. 1, No. 1 (1986), pp. 49\u201363.","journal-title":"Algorithmica"},{"key":"BF01553883_CR2","unstructured":"B. Baumgart: A polyhedral representation for computer vision.Proceedings of the AFIPS National Computer Conference, Anaheim, California, 1975, pp. 589\u2013596."},{"key":"BF01553883_CR3","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, Baltimore, 1985, pp. 135\u2013146.","DOI":"10.1145\/323233.323252"},{"key":"BF01553883_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/357337.357340","volume":"3","author":"B. Chazelle","year":"1984","unstructured":"B. Chazelle and J. Incerpi: Triangulation and shape complexity.ACM Transactions on Graphics, Vol. 3 (1984), pp. 135\u2013152.","journal-title":"ACM Transactions on Graphics"},{"issue":"No. 4","key":"BF01553883_CR5","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M. Garey","year":"1978","unstructured":"M. Garey, D. Johnson, F. Preparata, and R. Tarjan: Triangulating a simple polygon.Information Processing Letters, Vol. 7, No. 4 (1978), pp. 175\u2013180.","journal-title":"Information Processing Letters"},{"key":"BF01553883_CR6","doi-asserted-by":"crossref","unstructured":"S. K. Ghosh and D. M. Mount: An output sensitive algorithm for computing visibility graphs.Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, Los Angeles, 1987, pp. 11\u201319.","DOI":"10.1109\/SFCS.1987.6"},{"issue":"No. 2","key":"BF01553883_CR7","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, Vol. 2, No. 2 (1987), pp. 209\u2013233.","journal-title":"Algorithmica"},{"key":"BF01553883_CR8","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, Boulder, Colorado, 1977, pp. 49\u201360.","DOI":"10.1145\/800105.803395"},{"issue":"No. 2","key":"BF01553883_CR9","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. Guibas","year":"1985","unstructured":"L. Guibas and J. Stolfi: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Transactions on Graphics, Vol. 4, No. 2 (1985), pp. 74\u2013123.","journal-title":"ACM Transactions on Graphics"},{"key":"BF01553883_CR10","doi-asserted-by":"crossref","unstructured":"S. Hertel and K. Mehlhorn: Fast triangulation of a simple polygon.Proceedings of the Conference on Foundations of Computing Theory, New York, 1983, pp. 207\u2013218.","DOI":"10.1007\/3-540-12689-9_105"},{"key":"BF01553883_CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston and K. Mehlhorn: A new data structure for representing sorted lists.Acta Informatica, Vol. 17 (1982), pp. 157\u2013184.","journal-title":"Acta Informatica"},{"key":"BF01553883_CR12","unstructured":"S. Suri: Private communication, 1986."},{"issue":"No. 1","key":"BF01553883_CR13","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. Tarjan","year":"1988","unstructured":"R. Tarjan and C. Van Wyk: AnO(n log logn)-time algorithm for triangulating a simple polygon.SIAM Journal on Computing, Vol. 17, No. 1 (1988), pp. 143\u2013178.","journal-title":"SIAM Journal on Computing"},{"key":"BF01553883_CR14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E. Welzl","year":"1985","unstructured":"E. Welzl: Constructing the visibility graph forn line segments inO(n 2) time.Information Processing Letters, Vol. 20 (1985), pp. 167\u2013171.","journal-title":"Information Processing Letters"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553883.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01553883\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T01:16:45Z","timestamp":1586222205000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01553883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,6]]},"references-count":14,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1989,6]]}},"alternative-id":["BF01553883"],"URL":"https:\/\/doi.org\/10.1007\/bf01553883","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,6]]}}}