Home Bookmarks Papers Blog

A Practical Approach for Computing the Diameter of a Point-Set

Sariel Har-Peled

We present a new simple 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 algorithm can be implemented quickly, and it is robust. As such, this algorithm seems to be the algorithm of choice in practice for computing/approximating the diameter.
Postscript : PDF
Source code is avliable here.
Presentation - StarOffice

A nice competing algorithm was developed by Grgoire Malandain and Jean-Daniel Boissonnat. Their basic idea is completely different than the one underling this paper, as such their results are different.

See here.

   author    = "S.~{Har-Peled}",
   booktitle = SOCG_2001,
   title     = "A Practical Approach for Computing the Diameter
                of a Point-Set",
   year      = 2001,
   pages     = {177--186},

Last modified: Wed Feb 19 12:27:40 CST 2014