Approximation and Exact Algorithms for Minimum-Width Annuli and Shells
Home Bookmarks Papers Blog

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