We study the problem of reconstructing a simple polygon:Given a cyclically ordered vertex sequence of an unknown simple polygonP of n vertices and, for each vertex v of P, the sequence of angles definedby all the visible vertices of v in P, reconstruct the polygon P (up tosimilarity). An O(n~3log n) time algorithm has been proposed for thisproblem. We present an improved algorithm with running time O(n~2),based on new observations on the geometric structures of the problem.Since the input size (i.e., the total number of input visibility angles) isΘ(n~2) in the worst case, our algorithm is worst-case optimal.
展开▼
