Computing the Diameter of a Point Set

Grégoire Malandain (1) , Jean-Daniel Boissonnat (2)

1 EPIDAURE - Medical imaging and robotics
2 PRISME - Geometry, Algorithms and Robotics

Given a finite set of points ¸al P in ℝ^d, the diameter of ¸al P is defined as the maximum distance between two points of ¸al P. We propose a very simple algorithm to compute the diameter of a finite set of points. Although the algorithm is not worst-case optimal, an extensive experimental study has shown that it is extremely fast for a large variety of point distributions. In addition, we propose a comparison with the recent approach of Har-Peled and derive hybrid algorithms to combine advantages of both approaches.

Mots clés: computational geometry; diameter; width; approximation; point sets; furthest neighbors; double normal

Domaines: Imagerie médicale; Modélisation et simulation; Imagerie; Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Grégoire Malandain, Jean-Daniel Boissonnat. Computing the Diameter of a Point Set. International Journal of Computational Geometry and Applications, 2002, 12 (6), pp.489--510. ⟨inria-00615026⟩