Computing farthest pair of points in d dimensions

Question

Question: Given $n$ points in metric space, find a pair of points with the largest distance between them.

If we restrict ourselves to $d$-dimensional Euclidean space then, a naive algorithm of finding distances between all pairs of points in a space of dimension $d$ and selecting the maximum requires $O(dn^2)$ time.

However, finding a farthest pair for points in a plane can be done in time $O(n\log n)$. This is done by restricting our search to pairs of antipodal points on the convex hull. But, this approach does not scale well with higher dimensions.

Is there any solution better than the naive one either for the case $d=\Omega(n)$ (i.e., high dimensions) or for the case $d=O(\log \log n)$ (i.e., low dimensions)?

Answer 1

For the case $d = 3$, there exist $O(n\log n)$ algorithms due to Clarkson and Shor (randomized) and Ramos (deterministic). For higher dimensions there seem to exist only approximation algorithms, see for example a presentation of Vigneron. You can use the Johnson–Lindenstrauss lemma to reduce the problem (approximately) to dimension $O(\log n)$, in time $\tilde{O}(dn)$ (see for example Ailon and Chazelle).