pith. sign in

arxiv: 1801.02162 · v3 · pith:YJ7QUWZYnew · submitted 2018-01-07 · 💻 cs.CG

Reconstructing a convex polygon from its ω-cloud

classification 💻 cs.CG
keywords omegawedgecloudpolygonapexconditionsgivenrays
0
0 comments X
read the original abstract

An $\omega$-wedge is the closed set of 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 set of apex positions of all such placements of the $\omega$-wedge is called the $\omega$-cloud of $P$. 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$ and the two rays of the $\omega$-wedge in addition to the location of the apex. Here we consider the setting where the maximal $\omega$-cloud alone is given. We give two conditions under which it uniquely defines $P$: (i) when $\omega < \pi$ is fixed/given, or (ii) when what is known is that $\omega < \pi/2$. We show that if neither of these two conditions hold, then $P$ may not be unique. We show that, when the uniqueness conditions hold, the polygon $P$ can be reconstructed in $O(n)$ time with $O(1)$ working space in addition to the input, where $n$ is the number of arcs in the input $\omega$-cloud.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.