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 - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA
Duration: Jun 13 1999Jun 16 1999

Conference

ConferenceProceedings 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

    Agarwal, P. K., Aronov, B., Har-Peled, S., & Sharir, M. (1999). Approximation and exact algorithms for minimum-width annuli and shells. 380-389. Paper presented at Proceedings of the 1999 15th Annual Symposium on Computational Geometry, Miami Beach, FL, USA, . https://doi.org/10.1145/304893.304992