Approximation of planar convex sets from hyperplane probes (Q1364138)

The following geometric probing problem is considered: An unknown planar convex set is probed by an oracle which, when given a unit vector, returns the position of the corresponding supporting hyperplane. The author presents an on-line algorithm which, after \(n\) probes, gives inscribed and circumscribed polygons with a Hausdorff distance of \(O(n^{-2})\). This is optimal and an improvement on an algorithm of \textit{M. Lindenbaum} and \textit{A. Bruckstein} [IEEE Transactions on Pattern Analysis and Machine Intelligence 10, 517-529 (1994)].