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 OO contains OO 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 OO and each of the rays.#R##N##R##N#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−22n−2ω  -probes; if ω=π/2ω=π/2, the reconstruction uses 2n−32n−3ω  -probes. We show that both results are optimal. Let NBNB be the number of vertices of OO whose internal angle is at most ω  , (we show that 0≤NB≤30≤NB≤3). We determine the shape and orientation of a general convex n  -gon with NB=1NB=1 (respectively NB=2NB=2, NB=3NB=3) using 2n−12n−1 (respectively 2n+32n+3, 2n+52n+5) ω  -probes. We prove optimality for the first case. Assuming the algorithm knows the value of NBNB in advance, the reconstruction of OO with NB=2NB=2 or NB=3NB=3 can be achieved with 2n+22n+2 probes,- which is optimal.
['Prosenjit Bose', 'Jean-Lou De Carufel', 'Alina Shaikhet', 'Michiel H. M. Smid']
Probing convex polygons with a wedge