Information Processing Letters, 32 (1989), pp. 205-211.
Ömer Egecioglu and Bahman Kalantari
Approximating the Diameter of a Set of Points in the Euclidean Space
Abstract.
Given a set P with n points in R^k, its diameter, d_P, is the maximum of the
Euclidean distances between its points. We describe an algorithm that in m<= n
iterations obtains
r_1 < r_2 < .. < r_m <= d_P <= min{ sqrt{3}r_1, sqrt{5-2sqrt{3}}r_m}.
For k fixed, the cost of each iteration is O(n). In particular in the first
iteration, the algorithm produces an approximation r_1 which is within
sqrt{3} of d_P, independent of the dimension k.
omer@cs.ucsb.edu