A practical approach for computing the diameter of a point set

Research output: Contribution to conferencePaperpeer-review

Abstract

We present an approximation algorithm for computing the diameter of a point-set in d-dimensions. The new algorithm is sensitive to the "hardness" of computing the diameter of the given input, and for most inputs it is able to compute the exact diameter extremely fast. The new algorithm is simple, robust, has good empirical performance, and can be implemented quickly. As such, it seems to be the algorithm of choice in practice for computing/approximating the diameter.

Original languageEnglish (US)
Pages177-185
Number of pages9
DOIs
StatePublished - Jan 1 2001
Event17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States
Duration: Jun 3 2001Jun 5 2001

Other

Other17th Annual Symposium on Computational Geometry (SCG'01)
Country/TerritoryUnited States
CityMedford, MA
Period6/3/016/5/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A practical approach for computing the diameter of a point set'. Together they form a unique fingerprint.

Cite this