13
$\begingroup$

I have two sets $S,T$ of points in the 2-dimensional plane. I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as possible. How efficiently can this be done? Can it be done in $O(n \log n)$ time, where $n = |S|+|T|$?

I know that if I'm given a single set $S$, then it's possible to find the closest pair of points $s,s' \in S$ in $O(n \log n)$ time using a standard divide-and-conquer algorithm. However, that algorithm doesn't seem to generalize to the case of two sets, because there's no connection between the distance between the two closest points within $S$ or $T$ vs. the distance between the two closest points across those sets.

I thought of storing the set $T$ in a $k$-d tree, then for each $s \in S$, using a nearest-neighbor query to find the closest point in $T$ to $s$. However, the worst-case running time of this might be as bad as $O(n^2)$ time. There are results saying that if the points of $T$ are randomly distributed, then the expected running time for each query is $O(\log n)$, so we'd obtain an algorithm with expected running time $O(n \log n)$ if we were guaranteed that the points are randomly distributed -- but I'm looking for an algorithm that will work for any collection of points (not necessarily randomly distributed).

Motivation: An efficient algorithm would be useful for this other question.

$\endgroup$
0

3 Answers 3

13
$\begingroup$

Yes, this can be $O(n \log n)$ time. Build a Voronoi diagram for $T$. Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in. The center of that cell is the point $t \in T$ that is closest to $s$.

You can build a Voronoi diagram in $O(n \log n)$ time, and each query (find the cell containing $s$) can be done in $O(\log n)$ time, so the total running time is $O(n \log n)$ time.

$\endgroup$
5
  • $\begingroup$ Nice, much simpler than what I could come up with :). $\endgroup$
    – aelguindy
    Nov 5, 2016 at 4:05
  • $\begingroup$ Nice approach! Links would help though, especially for the query side of things. I could find a Wikipedia page showing that the general point location problem can be solved in $O(\log n)$ time, but is there a nicer way for the special case of Voronoi cells? My searching only turned up this answer, which does it the $O(n)$ way. $\endgroup$ Nov 5, 2016 at 14:49
  • $\begingroup$ The complexity of the Point Location problem is usually given in terms of the total number of vertices (here of the Voronoi Diagram). This number is likely larger than the number of points in $T$ and even $n = |S| + |T|$. I am not sure if the number of vertices is bounded by $\mathcal{O}(n)$, is it? $\endgroup$
    – Albjenow
    Nov 28, 2019 at 10:15
  • 1
    $\begingroup$ @Albjenow, I'm not sure if this addresses your concern, but yes, in 2 dimensions, I believe the number of vertices in a Voronoi diagram on $n$ points is $O(n)$ (I seem to recall it is $\le 6n$ or something like that). $\endgroup$
    – D.W.
    Nov 28, 2019 at 19:00
  • $\begingroup$ That seems correct as of this question on math.stackexchange. $\endgroup$
    – Albjenow
    Nov 29, 2019 at 7:00
5
$\begingroup$

I am expanding my comment into an answer, since I figured out a semi-satisfactory answer. This only solves the problem for $L^1$-distance. This answer is basically wrong.

This paper solves the problem of finding the closest pair of points in $d$ dimensions for the case when the sets are separated by a hyperplane in $O(n \log^{d-1} n)$.

For two dimensions, this solves the case in the answer you reference as your primary motivation for your question in $O(n \log n)$. It can also be used to solve the general case of the 2D problem in $O(n \log^2 n)$.

Given two sets $S, T$ of points in 2D, embed them in 3D space, displacing set $S$ by some $-\delta_z$ and set $T$ by $\delta_z$ in the $z$ direction. The choice of $\delta_z$ can be made to not affect the choice of the closest pair of points by taking $\delta_z$ to be smaller than the precision of your input points (and doubling the precision bits for each input coordinate). Use the 3D algorithm from the cited paper.

$\endgroup$
3
  • $\begingroup$ +1, but a couple of things about that paper (which I've only just started reading): (i) they only claim to solve the problem for the rectilinear (Manhattan) distance case; (ii) I don't understand why they think that region $P_2$ on p. 2 contains exactly 1 point. I had assumed that $p_m$ is the point in $P$ with median y co-ord in $P$, and $q_m$ is the point in $Q$ with median y co-ord in $Q$, but I don't see how the above could follow from this. $\endgroup$ Nov 5, 2016 at 14:45
  • 1
    $\begingroup$ @j_random_hacker the paper only solves the problem for L1 distance and this answer is wrong :). And I think that's the letter $l$ :). $\endgroup$
    – aelguindy
    Nov 5, 2016 at 15:44
  • $\begingroup$ Link is broken :( $\endgroup$ Dec 6, 2018 at 7:35
1
$\begingroup$

This can be done very easily with KDTrees. For example:

from sklearn.neighbors import KDTree
import numpy as np

n = 1000
a = np.random.random((n,3))
b = np.random.random((n,3))

tree = KDTree(a)
(distances, neighbors) = tree.query(b, k=1)

min_dist = distances.min()

The KDTree object enables assignments of nearest neighbors with a binary search. The tree.query function also has a dualtree=True argument that will use a tree for b as well that could be useful for larger trees. But for values of $n \le 10000$ I found dualtree=False (default) to be faster.

$\endgroup$
2
  • $\begingroup$ I don't see how this answers the question. I already discussed using k-d trees in the question and explained why I rejected them. My question is asking about worst-case running time, and k-d trees have a worst-case running time of $O(n^2)$. $\endgroup$
    – D.W.
    Aug 10, 2021 at 17:37
  • $\begingroup$ D.W. why do you think the worst-case running time is $O(n^2)$? $\endgroup$
    – AlexD
    Aug 11, 2021 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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