Computing a visibility polygon using few variables (Q396475)

This paper brings a novel approach for computing the visibility polygon of a given viewpoint inside of a simple polygon with both reflex and convex vertices. The visibility polygon is defined as the set of all points of the simple polygon that can be seen from the viewpoint, where two points (the given viewpoint and the point inside the simple polygon) can see each other whenever the segment given by these two points is contained in the simple polygon. The significant influence of reflex vertices on the visibility polygon is considered and the running time of the developed algorithms is expressed not only in terms of the complexity of the simple polygon but also in terms of the number of reflex vertices. Both the developed algorithms (output sensitive and a divide-and-conquer) described in the paper can be useful in computational geometry, robotics, video games, determining positions to locate facilities, etc.