9
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ What is the question here? $\endgroup$ – Raphael Jun 19 '12 at 19:19
  • 2
    $\begingroup$ Related question on cstheory.SE. $\endgroup$ – Raphael Jun 19 '12 at 19:20
  • $\begingroup$ I am not an expert but usually in machine learning, where this points are data, the sets behave well most of the time and are grouped together, so algorithms like the one suggested by @Pedro work well. $\endgroup$ – chazisop Jun 20 '12 at 8:24
  • 2
    $\begingroup$ "which obviously can be solved by LP in O(n) in 2-dimensional space" -- I wonder what prompted this statement. "Linear programming" is in general not solvable in linear time; the "linear" refers to something else. So does the LP has a special form? $\endgroup$ – Raphael Jun 21 '12 at 8:43
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ @Pedro: Sorry I didn't comment earlier (no time at the time). The reason I downvoted your answer was because it was a bad answer and should not have been at top. This is actually a well known problem in computational geometry with worst case O(n log n). A good answer would have pointed out the known problem (maybe with a reference) and the common solutions, which include: using k-d trees and testing elementwise, sweep algorithms, etc. The general idea should be to preprocess in an ordered structure and use that. Look at 1D case - more obvious O(n log n) there. $\endgroup$ – ex0du5 Jun 20 '12 at 21:31
  • 2
    $\begingroup$ @ex0du5: That sounds as if you should post your own answer! Note that "there is a better answer" is usually not a good reason for downvoting; this measure should be reserved for wrong, spam and very badly formatted answers. Pedro's is neither. See also here for an impression how much thought some people think should be given before a downvote. $\endgroup$ – Raphael Jun 21 '12 at 8:38
  • 1
    $\begingroup$ @Raphael: I didn't answer because there was one fair answer and I didn't have time to look up references. As for your reference on how to downvote, that is a horrible algorithm for these sites! CS students especially should understand the importance of not losing the goal for the formalism. The goal of the voting is to move answers to a ranking that will guide later students of the same problem to the most useful answers. My algorithm for voting does that. That algo: obviously not. This can be discussed on a meta if you like, but as adults, we should use our powers for good, I think. $\endgroup$ – ex0du5 Jun 21 '12 at 16:54
  • 1
    $\begingroup$ @ex0du5: You seem to have some time on your hands now. Can you actually show that this instance is actually a "well known problem with worst case $O(n\log n)$"? $\endgroup$ – Pedro Jun 21 '12 at 17:29
  • 1
    $\begingroup$ @ex0du5: Actually, nearest neighbour search, e.g. using k-d trees, has only average complexity O(logn). So we're back to square one. $\endgroup$ – Pedro Jun 21 '12 at 19:34
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Just a remark, one can also adapt the classic divide and conquer algorithm for closest pairs which also runs in $O(n \log{n})$; see also Wikipedia. $\endgroup$ – rizwanhudda Jun 20 '12 at 10:58
  • 1
    $\begingroup$ For a randomized linear time algorithm, see for example Rabin Flips a Coin on Lipton's blog. $\endgroup$ – Juho Jun 20 '12 at 11:01
  • 3
    $\begingroup$ Could you be a bit more specific about how you would implement this for disjoint sets, especially with regards to maintaining the $\mathcal O(n\log n)$ bound? $\endgroup$ – Pedro Jun 20 '12 at 21:48
  • $\begingroup$ -1 for incorrectness. The closest pair linesweep algorithm you link relies on the sorted set containing $O(1)$ elements, but in the case of disjoint sets, this set starts out containing $n$ elements, so it is no longer in $O(n\log n)$, at least not in the worst case. $\endgroup$ – Pedro Jun 21 '12 at 21:05
  • 1
    $\begingroup$ @Pedro: Why would it be larger? If anything, the set of current candidate points should shrink. $\endgroup$ – Raphael Jun 21 '12 at 21:32
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "Artium's solution, for instance, can be written in this form and is completely valid." -- well, what you propose here is no longer a (pure) sweep-line algorithm, so I don't know about that. $\endgroup$ – Raphael Jun 23 '12 at 8:51
  • $\begingroup$ @Raphael: Sure it is. Sweepline algorithms preprocess the points into an ordered structure just as described here. I even linked to Fortune's Algorithm under his answer, which shows the sweepline algorithm is just an instance of the Voronoi algorithm. The reason I kept the solution generic to the query structure is because there are a large number of geometric mechanisms that have been developed for this. $\endgroup$ – ex0du5 Jun 23 '12 at 13:28
  • $\begingroup$ You don't need a particular order while iterating over $B$, whereas the order is essential for (many/all?) sweepline algorithms (hence the name, I guess). $\endgroup$ – Raphael Jun 23 '12 at 15:09
1
$\begingroup$

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.

$\endgroup$

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.