An improved algorithm for reconstructing a simple polygon from its visibility angles

作者：Chen Danny Z; Wang Haitao^*

来源：Computational Geometry-Theory and Applications, 2012, 45(5-6): 254-257.

DOI：10.1016/j.comgeo.2012.01.005

• Polygon reconstruction
• Visibility angles
• Visibility graph

Given a cyclically ordered vertex sequence of an unknown simple polygon P of n vertices and, for each vertex v of P. the sequence of angles defined by all the visible vertices of v in P. we study the problem of reconstructing the polygon P (up to similarity). An O(n(3)logn) time algorithm has been proposed for this problem (by Disser, Mihalak, and Widmayer in 2011 [51]). We show in this paper that the running time of the algorithm in the previous work can be reduced to O(n(2)) time by new observations on the geometric structures of the problem.

• 出版日期2012-7