Computing the Diameter of a Point Set

Grégoire Malandain 1, * Jean-Daniel Boissonnat 2, *
* Auteur correspondant
1 EPIDAURE - Medical imaging and robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
2 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2002, 12 (6), pp.489--510
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00615026
Contributeur : Project-Team Asclepios <>
Soumis le : mercredi 17 août 2011 - 23:15:10
Dernière modification le : vendredi 16 novembre 2018 - 16:20:20
Document(s) archivé(s) le : vendredi 25 novembre 2011 - 11:26:15

Fichier

malandain-ijcga-2002.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00615026, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

225

Téléchargements de fichiers

435