An efficient approximation for point-set diameter in higher dimensions

Abstract

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/{\epsilon }^{d-1})$ time and $O(n)$ space, where $0<\epsilon ⩽1$. We also show that the proposed algorithm can be modified to a $(1+O(\epsilon ))$-approximation algorithm with $O(n+1/{\epsilon }^{\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.

References in corpus (1)

• Near-Optimal $\epsilon$-Kernel Construction and Related Problems