Approximation and Exact Algorithms for Minimum-Width Annuli and Shells

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

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/µ²).
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(n^3-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
}