Computing the Diameter of a Point SetReport as inadecuate

Computing the Diameter of a Point Set - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 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.

Keywords : computational geometry diameter width approximation point sets furthest neighbors double normal

Author: Grégoire Malandain - Jean-Daniel Boissonnat -



Related documents