Blind approximation of planar convex sets

Abstract

The process of learning the shape of an unknown convex planar object through an adaptive process of simple measurements called line probings, which reveal tangent lines to the object, is considered. A systematic probing strategy is suggested and an upper bound on the number of probings it requires for achieving an approximation with a pre-specified precision to the unknown object is derived. A lower bound on the number of probings required by any strategy for achieving such an approximation is also derived, showing that the gap between the number of probings required by the authors' strategy and the number of probings required by the optimal strategy is a logarithmic factor in the worst case. The proposed approach overcomes deficiencies of the classical geometric probing approach which is based on the polygonality assumption, and thus is not applicable for real robotic tasks.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>