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

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

Abstract

We prove the correctness of the linear-time algorithm in Joe and Simpson [7] for computing the visibility polygon of a simple polygon from a viewpoint that is either interior to the polygon or in its blocked exterior. This proof establishes pre- and post-conditions for all steps of the algorithm. The algorithm and the proof are identical for interior and blocked exterior viewpoints. Other algorithms for computing the visibility polygon (usually for interior viewpoints only) are either nonlinear-time and harder to implement or can fail for polygons that wind sufficiently.

Keywords:

• Computational geometry
• visibility
• algorithm correctness

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

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

Notes

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