Model-based probing strategies for convex polygons (Q1208433)

Geometric probing studies the power of different sensor models for reconstructing geometric objects. The authors seek probing strategies which completely determine a convex polygon. They use finger probes, where such probes measure the first point of contact between a direct line and the polygon. They are concerned with identifying an object and its orientation from a finite, predefined set of possible objects and they prove that \(n+4\) such finger probes are sufficient and \(n-1\) probes are necessary (optimal!) to determine the shape of a convex \(n\)-gon from a finite collection of models. For line probes they prove that \(2n+4\) probes are sufficient and \(2n-3\) necessary. The lower bound proof for line probes requires an exponential number of models. In the conclusions the authors give some interesting open problems, for instance the problem of model-based probing strategies.