Probing convex polygons with a wedge

Minimizing the number of probes is one of the main challenges in reconstructing geometric objects with probing devices. In this paper, we investigate the problem of using an ω-wedge probing tool to determine the exact shape and orientation of a convex polygon. An ω-wedge consists of two rays emanating from a point called the apex of the wedge and the two rays forming an angle ω. To probe with an ω-wedge, we set the direction that the apex of the probe has to follow, the line L→, and the initial orientation of the two rays. A valid ω-probe of a convex polygon O contains O within the ω-wedge and its outcome consists of the coordinates of the apex, the orientation of both rays and the coordinates of the closest (to the apex) points of contact between O and each of the rays. We present algorithms minimizing the number of probes and prove their optimality. In particular, we show how to reconstruct a convex n-gon (with all internal angles of size larger than ω) using 2n−2 ω-probes; if ω=π/2, the reconstruction uses 2n−3 ω-probes. We show that both results are optimal. Let NB be the number of vertices of O whose internal angle is at most ω, (we show that 0≤NB≤3). We determine the shape and orientation of a general convex n-gon with NB=1 (respectively NB=2, NB=3) using 2n−1 (respectively 2n+3, 2n+5) ω-probes. We prove optimality for the first case. Assuming the algorithm knows the value of NB in advance, the reconstruction of O with NB=2 or NB=3 can be achieved with 2n+2 probes,- which is optimal.

• View at Publisher
• View at Scopus