Given a finite set of pointsPinR^{d}, the diameter ofPis defined as the maximum distance between two points ofP. We propose a very simple algorithm to compute the diameter of a finite set of points. Although the algorithm is not worst-case optimal, it appears to be extremely fast for a large variety of point distributions.

- The implementation of the algorithm for computing/approximating
the diameter is available by anonymous ftp:
diameter-0.01.zip
or
diameter-0.01.tar.gz
- can be tested with real inputs or random distributions
- works for points in
*R*^{d} - contains also an implementation of Har-Peled's method (for the
exact computation of the diameter) that works in
*R*^{d}

- Research report
@TechReport{Malandain:Boissonnat:RR:2001, author = {Malandain, Grégoire and Boissonnat, Jean-Daniel}, title = {Computing the Diameter of a Point Set}, institution = {INRIA}, year = {2001}, type = {Research report}, number = {RR-4233}, address = {Sophia-Antipolis}, month = jul, url = "http://www.inria.fr/rrrt/rr-4233.html", keyword = {computational geometry} }

- Communication at
DGCI 2002
@InProceedings{malandain-boissonnat:dgci:2002, author = {Grégoire Malandain and Jean-Daniel Boissonnat}, title = {Computing the Diameter of a Point Set}, booktitle = {Discrete Geometry for Computer Imagery (DGCI 2002)}, OPTpages = {197--208}, year = {2002}, editor = {A. Braquelaire and J.-O. Lachaud and A. Vialard}, volume = {2301}, series = {LNCS}, address = {Bordeaux, France}, publisher = {Springer}, note = {also INRIA research report RR-4233}, keyword = {computational geometry} }

- Article in
*International Journal of Computational Geometry & Applications*@ARTICLE{malandain-boissonnat:ijcga:2002, AUTHOR = {Gr\'egoire Malandain and Jean-Daniel Boissonnat}, JOURNAL = {International Journal of Computational Geometry \& Applicatio ns}, TITLE = {Computing the Diameter of a Point Set}, YEAR = {2002}, MONTH = {December}, OPTNOTE = {}, NUMBER = {6}, PAGES = {489--510}, VOLUME = {12}

Gregoire Malandain Last modified: Tue Jul 19 09:43:26 MEST 2005