Approximation and Exact Algorithms for Minimum-Width Annuli and Shells

# Approximation and Exact Algorithms for Minimum-Width Annuli and Shells

#### Pankaj Agarwal, Boris Aronov, Sariel Har-Peled, and Micha Sharir.

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):
1. For d=2, we can compute in O(n log n) time an annulus containing S whose width is at most 2w*(S).
2. 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).
3. 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) µ))).
4. For d=3, we present an O(n3-1/19+µ)-time algorithm to compute a minimum-width shell containing S.

Appeared in 15th ACM Symp. of Comput. Geom., 1999
Appeared in Discrete & Computational Geometry
Postscript : PDF

```@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
}
```

Last modified: Fri Nov 14 11:18:16 CST 2014