An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles

2010/09/13 by Danny Z. Chen, Haitao Wang, Chen, Danny Z. +1
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS

paper · pdf · doi:10.48550/arxiv.1009.2521

12 pages, 6 figures

arxiv created 2010/09/13 · arxiv updated 2010/09/15

Abstract

In this paper, we study the following problem of reconstructing a simple polygon: 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, reconstruct the polygon P (up to similarity). An O(n³ log n) time algorithm has been proposed for this problem. We present an improved algorithm with running time O(n²), 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 O(n²) in the worst case, our algorithm is worst-case optimal.

Related

• Polygons with Prescribed Angles in 2D and 3D
• Pseudo-Triangle Visibility Graph: Characterization and Reconstruction
• Dynamic algorithms for visibility polygons in simple polygons
• Computing a visibility polygon using few variables
• Reconstructing Generalized Staircase Polygons with Uniform Step Length