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

Question

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.

Answer 1

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.

Answer 2

You can adapt the "closest pair" linesweep algorithm which is $O(n \log n)$.

The only change you will have to do is to ignore pairs that belong to the same set.

Edit: This is actually not simple (or even possible) as I described. See comments for discussion.

Answer 3

The idea in problems like this is to create an ordered structure from one of the sets that allows efficient queries of Nearest Neighbor. The classic paper that presented an O(log n) query structure for arbitrary dimension was:

Shamos and Hoey on Voronoi solutions

A number of other space partitions based on ideas from Delauney tesselations have been created since then, and these translate to a variety of subspace sweep descriptions as well. Note that the Voronoi method would also fall under a general divide-and-conquer description due to it's plane partitioning that makes the construction step O(n log n).

So, the basic solution to this problem is:

1. Take set A and build the efficient Nearest Neighbor query structure of your choice. This construction step is O(n log n) [see theorem 4].
2. For each element in B, query structure A for the nearest neighbor. Each query is O(log n) [see theorem 15, fixed dimension], so the total query time for all points in B is O(n log n).
3. When the result for the nearest point in A to each B is retrieved, put it in a structure ordered on the distance. This is O(log n) insert each result, or O(n log n) for all.
4. When all B have been looked at, you can quickly (O(1)) get the point B in the ordered structure with the smallest neighbor distance to a point in A.

As one can see looking at the complexity of each step, the total complexity is O(n log n). For the modern reader not looking at classic papers, this is covered in many algorithm books, e.g. "The Algorithm Design Manual" by Skiena.

Answer 4

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 in 2-dimensional space.

The Lower bound for this problem is $O(n*\log{n})$ under algebraic decision tree model. I will give a rough sketch of its proof here.

We will reduce the instance of Element distinctness problem E to C.

• Input to E: $S = \{a_1, a_2, a_3,...,a_n\}$
• Let $\epsilon$ > 0 be a a small fraction
• A = $\{(a_i,0) : 1 \leq i \leq n\}$, $B = \{(a_i + \epsilon) : 1 \leq i \leq n\}$
• Now If we can find the shortest distance (d) between sets A and B. We can decide the element distinctness problem in additional $O(n)$ time as follows
  • The set $S$ has a duplicate if and only if d = $\epsilon$

We know that the lower bound on runtime for deciding Element distinctness problem is $O(n*\log{n})$. Therefore, by reduction the lower bound also applies to our problem.

Answer 5

If you are using Python, you can use the implementation of sklearn pairwise_distances_argmin_min that given two point sets A and B returns the closest point pB in B and the distance from pA to pB for each point pA in A.

You then select the pair of points with the smallest distance of all in $O(n\log n)$:

from sklearn.metrics import pairwise_distances_argmin_min
import numpy as np

def get_closest_pair_of_points(point_list_1: List[Tuple[float]],
                           point_list_2: List[Tuple[float]]) -> Tuple[Tuple, Tuple, float]:
    """
    Determine the two points from two disjoint lists of points that are closest to 
    each other and the distance between them.

    Args:
        point_list_1: First list of points.
        point_list_2: Second list of points.

    Returns:
        Two points that make the closest distance and the distance between them.
    """
    indeces_of_closest_point_in_list_2, distances = pairwise_distances_argmin_min(point_list_1, point_list_2)

    # Get index of a point pair that makes the smallest distance.
    min_distance_pair_index = np.argmin(distances)

    # Get the two points that make this smallest distance.
    min_distance_pair_point_1 = point_list_1[min_distance_pair_index]
    min_distance_pair_point_2 = point_list_2[indeces_of_closest_point_in_list_2[min_distance_pair_index]]

    min_distance = distances[min_distance_pair_index]

    return min_distance_pair_point_1, min_distance_pair_point_2, min_distance

Of all implementations I have tested this is was fastest. It also does not have any limitations on the point distribution (such as two point sets being separable in space by a plane, etc.)