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.
@inproceedings{h-pacdp-01,
author = "S.~{Har-Peled}",
booktitle = SOCG_2001,
title = "A Practical Approach for Computing the Diameter
of a Point-Set",
year = 2001,
pages = {177--186},
}