Home | Bookmarks | Papers | Blog |

Let

- 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**, in time^{*}(S)**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**in time^{*}(S)**O((n)/(µ**or^{d}) log((\Diam(S))/(w^{*}(S) µ)))**O(((n log n)/(µ**.^{d-2}) +(n)/(µ^{d-1})) log((\Diam(S))/(w^{*}(S) µ))) - For
**d=3**, we present an**O(n**-time algorithm to compute a minimum-width shell containing^{3-1/19+µ})**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