A practical approach for computing the diameter of a point set

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.

REFERENCES

• 1: Pankaj K. Agarwal , Jiří Matoušek , Subhash Suri, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Computational Geometry: Theory and Applications, v.1 n.4, p.189-201, April 1992 [doi>10.1016/0925-7721(92)90001-9]
• 2: Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.82-91, January 17-19, 1999, Baltimore, Maryland, United States
• 3: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 4: Timothy M. Chan, Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus, Proceedings of the sixteenth annual symposium on Computational geometry, p.300-309, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336216]
• 5: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 6: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 7: Har-Peled, S. Source code of program for computing and approximating the diameter of a point-set in 3d, 2000. http://www.uiuc.edu/~sariel/papers/00/diameter /diam prog.html.
• 8: Large geometric models archive. Georgia Tech. http://www.cc.gatech.edu/projects/ large models/index.html.
• 9: Edgar A. Ramos, Deterministic algorithms for 3-D diameter and some 2-D lower envelopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.290-299, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336215]
• 10: Toussaint, G. T. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON '83 (1983), pp. A10.02/1-4.
• 11: P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory