6
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ UPDATE: We [1] were able to prove that an algorithm better than the naive $O(n^2d)$ is not possible under the Strong ETH for SAT, for $d=\Theta(\log n)$. [1] arxiv.org/abs/1608.03245 $\endgroup$ – Karthik C. S. Sep 2 '16 at 23:13
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thanks for the answer! I find it strange that there are no algorithms that do better than the naive approach for finding exact solutions in dimensions greater than 3. This is because there are algorithms better than the naive approach for the closest pair problem, which I felt was related to the farthest pair problem. $\endgroup$ – Karthik C. S. Jan 25 '16 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.