Approximation algorithms for minimum-width annuli and shells

Let S be a set of n points in R-d. The "roundness" of S can be measured by computing the width omega* = omega*(S) of the thinnest spherical shell (or annulus in R-2) that contains S. This paper contains two main results relat ed to computing an approximation of omega*: (i) For d = 2, we can compute i n O(n logn) time an annulus containing S whose width is at most 2 omega*(S) . We extend this algorithm, so that, for any given parameter epsilon > 0, a n annulus containing S whose width is at most (1 + epsilon)omega* is comput ed in time O(n log n + n/epsilon (2)). (ii) For d greater than or equal to 3, given a parameter epsilon > 0, we can compute a shell containing S of wi dth at most (1 + epsilon)omega* either in time O((n/epsilon (d))log(Delta/o mega*epsilon)) or in time O ((n/epsilon (d-2))(log n + 1/epsilon) log(Delta /omega*epsilon)), where Delta is the diameter of S.