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.
|Keywords||Probing, Reconstruction, Wedge|
Bose, P, De Carufel, J.-L. (Jean-Lou), Shaikhet, A. (Alina), & Smid, M. (2016). Probing convex polygons with a wedge. Computational Geometry, 58, 34–59. doi:10.1016/j.comgeo.2016.06.001