Approximation Algorithms for Minimum-Width Annuli and Shells

P. K. Agarwal, B. Aronov, S. Har-Peled, M. Sharir

    Research output: Contribution to journalArticlepeer-review


    Let S be a set of n points in ℝd. The "roundness" of S can be measured by computing the width ωz.ast; = ω*(S) of the thinnest spherical shell (or annulus in ℝ2) that contains S. This paper contains two main results related to computing an approximation of ω*: (i) For d = 2, we can compute in O(n log n) time an annulus containing S whose width is at most 2ω*(S). We extend this algorithm, so that, for any given parameter ε > 0, an annulus containing S whose width is at most (1 + ε)ω* is computed in time O(n log n + n/ε2). (ii) For d ≥ 3, given a parameter ε > 0, we can compute a shell containing S of width at most (1 + ε)ω* either in time O((n/εd) log(Δ/ω*ε)) or in time O((n/εd-2)(log n + 1/ε) log(Δ/ω*ε)), where Δ is the diameter of S.

    Original languageEnglish (US)
    Pages (from-to)687-705
    Number of pages19
    JournalDiscrete and Computational Geometry
    Issue number4
    StatePublished - Dec 2000

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics


    Dive into the research topics of 'Approximation Algorithms for Minimum-Width Annuli and Shells'. Together they form a unique fingerprint.

    Cite this