Given 2 sets of points in the plane, $A$ and $B$, each of size $n$, I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect.
The coordinates are comparable signed reals (no constraints here about that) and no 3 points are on the same line. There can be no segments sharing an end point because we need to construct $n$ pairs of points from $2n$ points, and there are no duplicate points.
I tried to sort each of the sets according to $x$ or $y$, and pair the appropriate points from each of the sorted sets, but I found a counterexample for that: a set of points whose sorted $x$ order was $(a_1,b_1,a_2,b_2)$ and sorted $y$ order was $(a_2,a_1,b_1,b_2)$.
