A practical approach for computing the diameter of a point set
- 1 June 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 177-186
- https://doi.org/10.1145/378583.378662
Abstract
We present an 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 {\em exact} diameter extremely fast. The new algorithm is simple, robust, has good empirical performance, and can be implemented quickly. As such, it seems to be the algorithm of choice in practice for computing/approximating the diameter.Keywords
This publication has 7 references indexed in Scilit:
- Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulusPublished by Association for Computing Machinery (ACM) ,2000
- Deterministic algorithms for 3-D diameter and some 2-D lower envelopesPublished by Association for Computing Machinery (ACM) ,2000
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fieldsJournal of the ACM, 1995
- FastMapPublished by Association for Computing Machinery (ACM) ,1995
- Farthest neighbors, maximum spanning trees and related problems in higher dimensionsComputational Geometry, 1992
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- AnO(n logn) algorithm for the all-nearest-neighbors ProblemDiscrete & Computational Geometry, 1989