Shortest distance between a point in A and a point in B

Problem Detail: 

Given two sets $A$ and $B$ each containing $n$ disjoint points in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \} $.

I am not sure if I am right, but this problem very similar to problems that can be solved by linear programming in computational geometry. However, the reduction to LP is not straightforward. Also my problem looks related to finding the thinnest stip between two sets of points which obviously can be solved by LP in $O(n)$ in 2-dimensional space.

Asked By : com

Answered By : Pedro

I have a solution which may seem a bit convoluted, but should be more efficient than the naive $\mathcal O(n^2)$ brute-force search:

1. let $v$ be the axis between the centres of mass of $A$ and $B$.
2. Sort the points in $A$ and $B$ along this axis in descending and ascending order respectively, resulting in the sequences $a_0$, $a_1$, ... , $a_n$ and $b_0$, $b_1$, ... , $b_n$.

The rest is in pseudo-code to make it clearer:

d = infinity. for j from 1 to n     if (b_1 - a_j) along v > d then break endif     for k from 1 to n         if (b_k - a_j) along v > d then             break         else             d = min( d , ||b_k - a_j|| )         endif     enddo enddo 

That is, by pre-sorting the points along $v$, you can filter out pairs that will never be within $d$ of each other since $b_k-a_j$ along $v$ will always be $\le \|b_k-a_j\|$.

In the worse case this is still $\mathcal O(n^2)$, but if $A$ and $B$ are well separated, it should be much faster than that, but not better than $\mathcal O(n\log n)$, which is required for the sorting.

Update

This solution is by no means pulled out of a hat. It's a special case of what I use in particle simulations to find all the interacting pairs of particles with spatial binning. My own work explaining the more general problem is here.

As for the suggestion to use a modified line-sweep algorithm, although intuitively simple, I'm not convinced that this is in $\mathcal O(n\log n)$ when disjoint sets are considered. The same goes for Rabin's randomized algorithm.

There doesn't seem to be much literature dealing with the closest pair problem in disjoint sets, but I've found this, which makes no claim to being under $\mathcal O(n^2)$, and this, which doesn't seem to make any claims about anything.

The algorithm above can be seen as a variant of the plane sweep suggested in the first paper (Shan, Zhang and Salzberg), yet instead of using the $x$-axis and no sorting, the axis between the sets is used and the sets are traversed in descending/ascending order.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2415