9
$\begingroup$

I'm just asking because I'm curious. I was seeking references on the following problem, that a friend exposed to me last holidays :

Problem

Given $n$ red points and $n$ blue points in the plane in general position (no 3 of them are aligned), find a pairing of the red points with the blue points such that the segments it draws are all disjoint.

This problem is always solvable, and admits several proof. A proof I know goes like this :

Start with an arbitrary pairing, and look for intersections of the segments it defines, if there are none you're done. If you found one, do the following operation :

r   r         r   r
 \ /          |   |
  X     =>    |   |
 / \          |   |
b   b         b   b

(uncross the crossing you have found), you may create new crossings with this operation. If you repeat this operation, you cannot cycle, because the triangle inequality shows that the sum of the length of the segments is strictly decreasing. So you will eventually get stuck at a configuration with no crossings.

Questions

  1. What is the complexity of the algorithm described in the proof ?
  2. What is the best known algorithm to solve this problem ?

I wouldn't be surprised to learn that this problem is a classic in computational geometry, however googling didn't give me references. Since some computational geometers are active on MO, I thought I could get interesting answers here.

Improve this question
$\endgroup$
5
  • $\begingroup$ You might gain insight by viewing each move as a transposition applied to a permutation, and looking at a directed graph of all permutations joined by edges when two permutations differ by a transposition and the direction goes from larger sum of lengths to smaller. This problem of traversing such a graph has likely been studied in combinatorics; I would be surprised to find an example that requires worse than O(n^2) moves. Gerhard "Ask Me About System Design" Paseman, 2012.01.28 $\endgroup$
    – Gerhard Paseman
    Jan 28, 2012 at 18:22
  • $\begingroup$ Try adding "ghostbusters" to your searches. $\endgroup$
    – Zsbán Ambrus
    Jan 28, 2012 at 19:50
  • $\begingroup$ Note that you could also solve a minimal weight matching problem on a weighted bipartite graph where the edge weights are the distances of red points from blue points. This has $ O(n^3) $ runtime, still polynomial but asymptotically slower than the algorithms suggested in the answers. $\endgroup$
    – Zsbán Ambrus
    Jan 28, 2012 at 21:57
  • $\begingroup$ Thanks to all for your replies and comments. I knew how to prove the existence with the ham sandwich theorem but wasn't sure how efficient it was as an algorithm. $\endgroup$
    – Thomas Richard
    Jan 29, 2012 at 9:59
  • $\begingroup$ Could we tag this with [co.combinatorics]? I think the part of the question that's still unanswered, that is, whether if you naively uncross edges it may take more than polynomial time to arrive at a non-crossing matching, is a combinatorial question. $\endgroup$
    – Zsbán Ambrus
    Feb 15, 2012 at 10:16

3 Answers 3

Reset to default
11
$\begingroup$

The Ghosts and Ghostbusters problem can be solved in $O(n\log n)$ time, which is considerably faster than the $O(n^2\log n)$-time algorithm suggested by CLRS.

The ham sandwich theorem implies that there is a line $L$ that splits both the ghosts and the ghostbusters exactly in half. (If the number of ghosts and ghostbusters is odd, the line passes through one of each; if the number is even, the line passes through neither.) Lo, Matoušek, and Steiger [Discrete Comput. Geom. 1994] describe an algorithm to compute a ham-sandwich line in $O(n)$ time; their algorithm is also sketched here. Now recursively solve the problem on both sides of $L$; the recursion stops when all subsets are empty. The total running time obeys the mergesort recurrence $T(n) = O(n) + 2T(n/2)$ and thus is $O(n\log n)$.

This algorithm is optimal in the algebraic decision tree and algebraic computation tree models of computation, because you need $\Omega(n\log n)$ time in those models just to decide whether two sets of $n$ points are equal.

Improve this answer
$\endgroup$
3
$\begingroup$

Check out the classic Cormen, Leiserson, Rivest, Stein, ''Introduction to algorithms'', second edition. In chapter 33 (Computational Geometry). See the exercises at the end of the whole chapter: exercise 33-3 is your problem. The full solution isn't described, but you will find a hint for a polynomial time algorithm. I have no idea whether that's the fastest algorithm known.

Improve this answer
$\endgroup$
2
$\begingroup$

In the paper Geometry Helps in Matching, by P. Vaidya, he shows that the minimum matching (which is what you are finding here) can be found in $O(n^2 \log^3(n))$ time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The abstract of that paper claims that they can get $ O(n^2 log^3 n) $ time only in the case of $ L_1 $ and $ L_\infty $ metrics (those two are the same in 2 dimensions of course). They give a somewhat slower algorithm for the $ L_2 $ case. Does a minimal total length in $ L_\infty $ metric guarantee no intersections between the segments? $\endgroup$
    – Zsbán Ambrus
    Jan 29, 2012 at 11:05
  • $\begingroup$ The triangle inequality in those metrics is Minkowski's inequality, so certainly $L_1$ should work... $\endgroup$
    – Igor Rivin
    Jan 29, 2012 at 16:11
  • $\begingroup$ No way. The triangle inequality proof only works with L_2 because you can break up the crossing segments to two smaller segments at their intersection points. In fact, consider the two red points a = (0, 0), b = (1, 0), and the two black points c = (1, 2), d = (2, 2). Then the matching a-c, b-d has total $ L_\infty $ length 3 + 3 = 6; but the matching a-d, b-c which has segments crossing each other has total $ L_\infty $ length 4 + 2 = 6, so a matching shortest in $ L_\infty $ need not be non-crossing. $\endgroup$
    – Zsbán Ambrus
    Jan 30, 2012 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.