Approximation of Planar Convex Sets from Hyperplane Probes

This paper studies a geometric probing problem. Suppose that an unknown convex set in R ² can be probed by an oracle which, when given a unit vector, will return the position of the supporting hyperplane of the convex set that has the given vector as an outward normal. We present an on-line algorithm for choosing probing directions so that, after n probes, an inner and an outer estimate of the convex set are obtained that are within of each other in Hausdorff distance. This is optimal since there exist convex sets that, even if visible, cannot be approximated better than with n-sided polygons, for example, a circle. Received April 18, 1995, and in revised form March 28, 1996.