Cheap and Secure Web Hosting Provider : See Now

[Solved]: Constructing non intersecting segments from distinct sets of points

, , No Comments
Problem Detail: 

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

Asked By : NightRa

Answered By : Joseph O'Rourke

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.


Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback