On the correctness of a linear-time visibility polygon algorithm Footnote^∗

^∗This work was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada

References

• Chazelle , B. 1982 . Proceedings of 23rd IEEE Symposium on Foundations of Computer Science . A theorem on polygon cutting with applications . 1982 . pp. 339 – 349 .
   Google Scholar
• Gindy , H. El and Avis , D. 1981 . A linear algorithm for computing the visibility polygon from a point . J. Algorithms , 2 : 186 – 197 .
   Google Scholar
• Freeman , H. and Loutrel , P. P. 1967 . An algorithm for the solution of the two-dimensional hidden-line problem . IEEE Trans. on Electronic Computers , EC-16 : 784 – 790 .
   Google Scholar
• Guibas , L. , Hershberger , J. , Leven , D. , Sharir , M. and Tarjan , R. E. 1987 . Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons . Algorithmica , 2 : 209 – 233 .
   Google Scholar
• Henrici , P. 1974 . Applied and Computational Complex Analysis , John Wiley & Sons .
   Google Scholar
• Joe , B. and Simpson , R. B. 1986 . Triangular meshes for regions of complicated shape . Int. J. for Num. Meth. in Eng. , 23 : 751 – 778 .
   Google Scholar
• Joe , B. and Simpson , R. B. 1987 . Corrections to Lee's visibility polygon algorithm . BIT , 27 : 458 – 473 .
   Google Scholar
• Lee , D. T. 1983 . Visibility of a simple polygon . Computer Vision, Graphics, and Image Processing , 22 : 207 – 221 .
   Google Scholar
• Schachter , B. 1978 . Decomposition of polygons into convex sets . IEEE Trans. on Comp. , C-27 : 1078 – 1082 .
   Google Scholar
• Tarjan , R. E. and Van Wyk , C. J. 1988 . An O(n log log n) time algorithm for triangulating a simple polygon . SIAM J. Comput. , 17 : 143 – 178 .
   Google Scholar