2
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

Here is a quote from

Kaneko, Atsushi, and Mikio Kano. "Discrete Geometry on Red and Blue Points in the Plane—A Survey." Discrete and Computational Geometry. Springer Berlin Heidelberg, 2003. 551-570.


  Survey


$\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.