Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414821 | Computational Geometry | 2011 | 9 Pages |
Abstract
We study the problem of reconstructing a simple polygon from angles measured at the vertices of the polygon. We assume that at each vertex v a sensing device returns a list of angles α1,α2,…α1,α2,…, where αiαi is the angle between the i -th and the (i+1)(i+1)-th vertices visible to v in counterclockwise (ccw) order starting with the ccw neighbor of v along the boundary. We prove that the angle measurements at all vertices of a simple polygon together with the order of the vertices along the boundary uniquely determine the polygon (up to similarity). In addition, we give an algorithm for reconstructing the polygon from this information in polynomial time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yann Disser, Matúš Mihalák, Peter Widmayer,