Parallel strategies for geometric probing

Abstract

The problem of recovering the shape of planar objects from line or finger probings arises in robotics. This problem is addressed under the assumption that composite probings are made. One composite probing comprises several (k) line or finger probings done simultaneously. An investigation is conducted of planar polygon reconstruction from sequences of composite k-probings. For every value of k, a lower bound on the number of k-probings required for reconstruction under any strategy is obtained. Specific strategies which are provably almost optimal are provided.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>