Approximation and exact algorithms for minimum-width annuli and shells

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

    Research output: Contribution to conferencePaper

    Abstract

    The approximation and the exact algorithms to compute the minimum-width shell or annulus are discussed. To measure the S or the roundness of a set of n points in Rd, the S can be approximated with a sphere (Γ) so that the maximum distance between a point of S and Γ is minimized. It was found that the problem of measuring the roundness of S is equivalent to computing a shell of the smallest width that contains S.

    Original languageEnglish (US)
    Pages380-389
    Number of pages10
    DOIs
    StatePublished - 1999
    EventProceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA
    Duration: Jun 13 1999Jun 16 1999

    Other

    OtherProceedings of the 1999 15th Annual Symposium on Computational Geometry
    CityMiami Beach, FL, USA
    Period6/13/996/16/99

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Approximation and exact algorithms for minimum-width annuli and shells'. Together they form a unique fingerprint.

    Cite this