Cheap and Secure Web Hosting Provider : See Now

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

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

#### 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 : http://cs.stackexchange.com/questions/35698

3.2K people like this