11
$\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$
10
$\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$
  • $\begingroup$ Nice, much simpler than what I could come up with :). $\endgroup$ – aelguindy Nov 5 '16 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$ – j_random_hacker Nov 5 '16 at 14:49
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$
  • $\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$ – j_random_hacker Nov 5 '16 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 '16 at 15:44
  • $\begingroup$ Link is broken :( $\endgroup$ – Keerthana Gopalakrishnan Dec 6 '18 at 7:35

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.