{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:50:15Z","timestamp":1759683015089},"publisher-location":"Berlin\/Heidelberg","reference-count":18,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540543430"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028282","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T05:52:14Z","timestamp":1132638734000},"page":"437-448","source":"Crossref","is-referenced-by-count":3,"title":["An optimal algorithm for computing visibility in the plane"],"prefix":"10.1007","author":[{"given":"Paul J.","family":"Heffernan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","unstructured":"E. Arkin and J.S.B. Mitchell, \u201cAn Optimal Visibility Algorithm for a Simple Polygon With Star-Shaped Holes\u201d, Technical Report No. 746 School of Operations Research and Industrial Engineering, Cornell University, June, 1987."},{"key":"39_CR2","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, \u201cVisibility of Disjoint Polygons\u201d, Algorithmica, Vol. 1, (1986), pp. 49\u201363.","journal-title":"Algorithmica"},{"key":"39_CR3","unstructured":"R. Bar-Yehuda and B. Chazelle, private communication, 1991."},{"key":"39_CR4","unstructured":"R. Bar-Yehuda and R. Grinwald, \u201cAn O(N+N 1+\u2208 )-Time Algorithm to Merge H Simple Polygons\u201d, Technical Report 657, Computer Science Dept., Technion, 1990."},{"key":"39_CR5","unstructured":"B. Chazelle, \u201cTriangulating a Simple Polygon in Linear Time\u201d, CS-TR-264-90, Princeton Univ., May 1990."},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"K. Clarkson, R.E. Tarjan, C. Van Wyk, \u201cA Fast Las Vegas Algorithm for Triangulating a Simple Polygon\u201d, Proc. Fourth Annual ACM Symposium on Computational Geometry, pp. 18\u201322, 1988. Also Princeton Technical Report CS-TR-157-88.","DOI":"10.1145\/73393.73396"},{"key":"39_CR7","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H.A. Gindy El","year":"1981","unstructured":"H.A. El Gindy and D. Avis, \u201cA Linear Algorithm for Computing the Visibility Polygon From a Point\u201d, Journal of Algorithms, Vol. 2 (1981), pp. 186\u2013197.","journal-title":"Journal of Algorithms"},{"key":"39_CR8","unstructured":"P.J. Heffernan and J.S.B. Mitchell, \u201cAn Optimal Algorithm for Computing Visibility in the Plane\u201d, Technical Report No. 953, School of Operations Research and Industrial Engineering, Cornell University, 1990."},{"key":"39_CR9","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1007\/BF01937271","volume":"27","author":"B. Joe","year":"1987","unstructured":"B. Joe and R.B. Simpson, \u201cCorrection to Lee's Visibility Polygon Algorithm\u201d, BIT, 27 (1987), pp. 458\u2013473.","journal-title":"BIT"},{"issue":"1","key":"39_CR10","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"D.G. Kirkpatrick, \u201cOptimal Search in Planar Subdivisions\u201d, SIAM Journal on Computing, 12 (1983), No. 1, pp. 28\u201335.","journal-title":"SIAM Journal on Computing"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick, M.M. Klawe, and R.E. Tarjan, \u201cPolygon Triangulation in O(n log log n) Time with Simple Data-Structures\u201d, Proc. Sixth Annual ACM Symposium on Computational Geometry, Berkeley, CA, June 6\u20138, 1990, pp. 34\u201343.","DOI":"10.1145\/98524.98533"},{"key":"39_CR12","unstructured":"D.T. Lee, \u201cProximity and Reachability in the Plane\u201d, Ph.D. Thesis, Report R-831, Dept. of Electrical Engineering, University of Illinois at Urbana-Champaign, Nov. 1978."},{"key":"39_CR13","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, \u201cVisibility of a Simple Polygon\u201d, Computer Vision, Graphics, and Image Processing, Vol. 22 (1983), pp. 207\u2013221.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"39_CR14","unstructured":"J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987."},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"R. Seidel, \u201cA Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons\u201d, Manuscript, October, 1990.","DOI":"10.1016\/0925-7721(91)90012-4"},{"key":"39_CR16","series-title":"NATO ASI Series","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-642-83539-1_9","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"M. Sharir","year":"1988","unstructured":"M. Sharir, \u201cDavenport-Schinzel Sequences and their Geometric Applications\u201d, pp 253\u2013278, NATO ASI Series, Vol. F40, Theoretical Foundations of Computer Graphics and CAD, R.A. Earnshaw (Ed.), Springer-Verlag Berlin Heidelberg, 1988."},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"S. Suri and J. O'Rourke, \u201cWorst-Case Optimal Algorithms For Constructing Visibility Polygons With Holes\u201d, Proc. Second Annual ACM Symposium on Computational Geometry, Yorktown Heights, NY, June 1986, pp. 14\u201323.","DOI":"10.1145\/10515.10517"},{"issue":"1","key":"39_CR18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R.E. Tarjan","year":"1988","unstructured":"R.E. Tarjan and C. Van Wyk, \u201cAn O(n log log n)-Time Algorithm for Triangulating a Simple Polygon\u201d, SIAM Journal on Computing, 17 (1988), No. 1, pp. 143\u2013178.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028282.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:58:44Z","timestamp":1607551124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0028282","relation":{},"subject":[]}}