The problem: http://ruffnsluff.blogspot.com/2017/02/dont-cross-streams.html
$N$ red and $N$ blue 2D points, no three collinear. Show that we can pair them off (red with blue) such that the line segment don't cross.
Solution
This has an elegant existential solution (don't know the source).
Of all the possible pairings, pick the pairing which minimizes the sum of the lengths of line segments. No two line segments of this will cross!
Suppose $A,B,C,D$ are points with $A,B$ red and $C,D$ blue such that $AC$ and $BD$ cross (say at $E$).
In the triangles $BEC$ and $AED$ we have that $BE + EC \gt BC$ and $AE + ED \gt AD$ and so $AC + BD \gt AD + BC$.
Uncrossing will reduce the sum of the lengths of the line segments.
There are also constructive solutions, which lead to $O(n^2\log n)$ time algorithms.
$N$ red and $N$ blue 2D points, no three collinear. Show that we can pair them off (red with blue) such that the line segment don't cross.
Solution
This has an elegant existential solution (don't know the source).
Of all the possible pairings, pick the pairing which minimizes the sum of the lengths of line segments. No two line segments of this will cross!
Suppose $A,B,C,D$ are points with $A,B$ red and $C,D$ blue such that $AC$ and $BD$ cross (say at $E$).
In the triangles $BEC$ and $AED$ we have that $BE + EC \gt BC$ and $AE + ED \gt AD$ and so $AC + BD \gt AD + BC$.
Uncrossing will reduce the sum of the lengths of the line segments.
There are also constructive solutions, which lead to $O(n^2\log n)$ time algorithms.
No comments:
Post a Comment