A Linear Time Algorithm for Triangulating a Point-Visible Polygon

The triangulation of a point-visible (star-shaped) polygon cannot be performed trivially if its kernel does not share a vertex with the polygon. The paper presents a triangulation algorithm that exploits point-and strong edge-visibility. It is through these two properties that the authors are able to triangulate in linear time. After classifying simple polygons by visibility, the authors show that…