Reconstructing a convex polygon from its ω-cloud
share
An ω-wedge is the (closed) set of all points contained between two rays that are emanating from a single point (the apex), and are separated by an angle ω < π. Given a convex polygon P, we place the ω-wedge such that P is inside the wedge and both rays are tangent to P. The ω-cloud of P is the curve traced by the apex of the ω-wedge as it rotates around P while maintaining tangency in both rays. We investigate reconstructing a polygon P from its ω-cloud. Previous work on reconstructing P from probes with the ω-wedge required knowledge of the points of tangency between P the two rays of the ω-wedge. Here we show that if ω is known, the ω-cloud alone uniquely determines P, and we give a linear-time reconstruction algorithm. Furthermore, even if we only know that ω < π/2, we can still reconstruct P, albeit in cubic time in the number of vertices. This reduces to quadratic time if in addition we are given the location of one of the vertices of P.
READ FULL TEXT