Approximation and exact algorithms for minimum-width annuli and shells
Pankaj K. Agarwal, Boris S. Aronov, Sariel Har-Peled, Micha Sharir · 1999
Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper contains three main results related to computing ! : (i) For d = 2, we can compute in O(n log n) time an annulus containing S whose width is at most 2! (S). We extend this algorithm, so that for any given parameter " ? 0, an annulus containing S whose width is at most (1 + ")! , is computed in time O(n log n + n=" 2 ). (ii) For d 3, given a parameter " ? 0, we can compute a shell containing S of width at most (1+ ")! either in time O \\Gamma n " d log( \\Delta ! " ) \\Delta or in time O \\Gamma n " d\\Gamma2 \\Gamma log n + 1 " \\Delta log \\Gamma \\Delta ! " \\Delta\\Delta . Work by P.A. was supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA--9870724, and CCR--9732787, by an NYI award, and by a grant from ...