An efficient approximation for point-set diameter in higher dimensions

In this paper, 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+\epsilon )$-approximation algorithm with $O(n+ 1/\varepsilon^{d-1})$timeand$O(n)$space,where$0 < \varepsilon\leqslant 1$\mathrm{.}Wealsoshowthattheproposedalgorithmcanbemodifiedtoa$(1+O(\varepsilon))$-approximationalgorithmwith$O(n+ 1/\varepsilon^{\frac{2d}{3}-\frac{1}{3}})$ running time. These results provide some improvements in comparison with existing algorithms in terms of simplicity and data structure.