T. J. Richardson1
Abstract. This paper studies a geometric probing problem. Suppose that an unknown convex set in
R
2
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.