Reconstructing a convex polygon from its $\omega$-cloud
Prosenjit K. Bose, Jean-Lou De Carufel, Elena Khramtcova, Sander Verdonschot · arXiv (Cornell University) · 2018
An $\omega$-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 $\omega < \pi$. Given a convex polygon $P$, we place the $\omega$-wedge such that $P$ is inside the wedge and both rays are tangent to $P$. The $\omega$-cloud of $P$ is the curve traced by the apex of the $\omega$-wedge as it rotates around $P$ while maintaining tangency in both rays. We investigate reconstructing a polygon $P$ from its $\omega$-cloud. Previous work on reconstructing $P$ from probes with the $\omega$-wedge required knowledge of the points of tangency between $P$ the two rays of the $\omega$-wedge. Here we show that if $\omega$ is known, the $\omega$-cloud alone uniquely determines $P$, and we give a linear-time reconstruction algorithm. Furthermore, even if we only know that $\omega < \pi/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$.