Better approximation algorithm for point-set diameter

Abstract

We propose a new $(1+O(\epsilon ))$-approximation algorithm with $O(n+1/{\epsilon }^{\frac{(d-1)}{2}})$ running time for computing the diameter of a set of $n$ points in the $d$-dimensional Euclidean space for a fixed dimension $d$, where $0<\epsilon ⩽1$. This result provides some improvements in the running time of this problem in comparison with previous algorithms.

arXiv admin note: substantial text overlap with arXiv:1610.08543