DocumentCode :
3718784
Title :
Pseudo-triangulating a simple polygon from its visibility graph
Author :
Zahra Sadat Emamy
Author_Institution :
Dept. of Math. Sci., Sharif Univ. of Technol., Tehran, Iran
fYear :
2015
Firstpage :
106
Lastpage :
111
Abstract :
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.
Keywords :
Geometry
Publisher :
ieee
Conference_Titel :
Computer and Knowledge Engineering (ICCKE), 2015 5th International Conference on
Type :
conf
DOI :
10.1109/ICCKE.2015.7365868
Filename :
7365868
Link To Document :
بازگشت