## Complexity of matching red and blue points in the plane.

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

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 – Gerhard Paseman Jan 28 2012 at 18:22
Try adding "ghostbusters" to your searches.  – Zsbán Ambrus Jan 28 2012 at 19:50
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.  – Zsbán Ambrus Jan 28 2012 at 21:57
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. – Thomas Richard Jan 29 2012 at 9:59
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.  – Zsbán Ambrus Feb 15 2012 at 10:16

## 3 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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.

-

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? – Zsbán Ambrus Jan 29 2012 at 11:05
The triangle inequality in those metrics is Minkowski's inequality, so certainly $L_1$ should work... – Igor Rivin Jan 29 2012 at 16:11
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.   – Zsbán Ambrus Jan 30 2012 at 9:05
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9400143027305603, "perplexity_flag": "middle"}