Advertisement
Published in:
2011 | OriginalPaper | Chapter
An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles
Authors : Danny Z. Chen, Haitao Wang
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the 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
3
log
n
) time algorithm has been proposed for this problem. 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.