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

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

2010-09-13

arxiv.org/abs/1009.2521v1

Computer Science

Computational Geometry

12 pages, 6 figures

Scientific paper

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^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 O(n^2) in the worst case, our algorithm is worst-case optimal.

Affiliated with

Also associated with

No associations

Rating

An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394434