Let S be a set of n points in R d.
The ``roundness'' of S can be measured by computing the width
w*(S) of the thinnest spherical shell (or annulus in
R2) that contains S. This paper contains four
main results related to computing w*(S):
For d=2, we can compute in O(n log n) time an
annulus containing S whose width is at most
2w*(S).
For d=2 we can compute, for any given parameter
µ>0, an annulus containing S whose width is at most
(1+µ)w*(S), in time O(n log n +
n/µ2).
For d >= 3, given a
parameter µ > 0, we can compute a shell containing S
of width at most (1+µ)w*(S) in time
O((n)/(µd) log((\Diam(S))/(w*(S)
µ))) or O(((n log n)/(µd-2)
+(n)/(µd-1)) log((\Diam(S))/(w*(S)
µ))).
For d=3, we present an
O(n3-1/19+µ)-time algorithm
to compute a minimum-width shell containing S.
@article{aahs-aeamw-00,
author = {P.~K.~Agarwal and B.~Aronov and S.~Har-Peled and M.~Sharir},
title = {Approximation and Exact Algorithms for Minimum-Width
Annuli and Shells},
journal = "Discrete Comput. Geom.",
pages = "687--705",
volume = {24},
number = {4},
year = 2000
}