Pseudo-triangulating a simple polygon from its visibility graph

摘要

Visibility graph of a simple polygon in a plain is a graph in which the number of its vertices corresponds with the number of vertices in the polygon and each of its edges corresponds with a pair of visible vertices in the polygon. Visibility graph reconstruction of a polygon is one of the old and important problems in computational geometry for which no algorithm has been offered yet. Considering that the problem of visibility graph reconstruction of a pseudo-triangle has been solved, we present an O(n2)-time algorithm for pseudo-triangulation of a simple polygon, using the visibility graph corresponding with the polygon (n is number of vertices of the polygon). To do so, first we present a method for triangulation of a simple polygon, using the visibility graph. Then, using the properties about the polygon, we gained from the visibility graph, we represent a pseudo-triangulation of the polygon.