6
$\begingroup$

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance between $u$ and $v$ (may be considered as points or vectors). Also what's the most efficient algorithm to determine $u$ and $v$ (not necessarily unique) such that $d(u,v)$ is minimized?


So minimizing $d(u,v)$ is pretty much the same as minimizing $[d(u,v)]^2$, which can be written using the distance formula. But I couldn't think of anything better than a brute-force $O(|A||B|)$ solution (where $|A|$ denotes the cardinality of $A$) which tries every possible $u\in A,v\in B$.

$\endgroup$
0
$\begingroup$

Here's an $O(n \log n)$ algorithm that works for all possible sets $A$ and $B$.

Let $n = |A| + |B|$.

This question has been asked in other platforms (here or here), but none of them give satisfactory answers (...at least to me. I cannot verify that they work in the claimed time for all possible inputs. For example, using KD tree does not guarantee $O(n \log n)$ unless the points are sufficiently random. The answer to second link is even more evil).

So, here's a purely $O(n \log n)$ algorithm to solve this! Good thing you asked this in a math forum, because despite being theoretically interesting, I wouldn't want to implement it...

First, construct the voronoi diagram $V_A$ of all the points in $A$. For each point $b_j \in B$, find the voronoi cell $v_i \in V_A$ that contains the point -- by the property of a voronoi diagram, we know that $a_i$ is the closest neighbor of $b_j$. Thus, by doing this for all points in $B$ and taking the minimum, we get the pair with minimum distance.

Of course, that's assuming we are able to find the cell $v_i$ for each point $b_i$ quickly. To do it quickly, we use the sweep line algorithm: sweep all the points in the voronoi diagram $V_A$ and the points $B$. We store the current partition of the space using a binary tree so that whenever the sweep line encounters a point $b_i \in B$, we are able to find the voronoi diagram containing $b_i$ in $O(\log n)$. Whenever we encounter a point $a_i \in A$, we update the tree from the structure of the voronoi diagram. This sweep line is rather analogous to the sweep line performed for the "find intersecting lines" algorithm.

Since construction of a voronoi diagram takes $O(n \log n)$ time, the entire procedure is $O(n \log n)$.

$\endgroup$
  • $\begingroup$ Btw, a balanced $k$d tree can be computed in $O(kn\log n)$ which will give the worst case guarantees you’d need for the other answer. $\endgroup$ – adfriedman Sep 3 '19 at 3:15

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.