Abstract : Visibility graph of a polygon corresponds to its internal diagonals and boundary edges. For each vertex on the boundary of the polygon, we have a vertex in this graph and if two vertices of the polygon see each other there is an edge between their corresponding vertices in the graph. Two vertices of a polygon see each other if and only if their connecting line segment completely lies inside the polygon. Recognizing visibility graphs is the problem of deciding whether there is a simple polygon whose visibility graph is isomorphic to a given graph. Another important problem is to reconstruct such a polygon if there is any. These are well-known and well-studied, but yet open problems in geometric graphs and computational geometry. However, these problems have been solved efficiently for special cases where the target polygon is known to be a tower or a spiral polygon. In this paper, we solve these recognizing and reconstruction problems for another type of polygons, named anchor polygons.
https://hal.inria.fr/hal-01446265 Contributor : Hal IfipConnect in order to contact the contributor Submitted on : Wednesday, January 25, 2017 - 4:50:58 PM Last modification on : Friday, March 2, 2018 - 3:04:02 PM Long-term archiving on: : Wednesday, April 26, 2017 - 4:01:49 PM