Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions

We study the problem of computing the diameter of a set of n points in d-dimensional Euclidean space for a fixed dimension d, and propose a new (1+ε)-approximation algorithm with O(n+1/εd−1) time and O(n) space, where 0<ε⩽1. We also show that the proposed algorithm can be modified to a (1+O(ε))-approximation algorithm with O(n+1/ε2d3−12) running time. Our proposed algorithms are different with the previous algorithms in terms of computational technique and data structures. These results provide some improvements in comparison with existing algorithms in terms of simplicity and data structure.