Connect an even number of nodes without crossing

Question

I have two sets of n nodes. Now I want to connect each node from one set with another node from another set. The resulting graph must not have intersections.

I know a few sweep line algorithms ( Bentley-Ottmann-Algorithm to check where intersections occur, but I could not find an algorithm to solve these intersections, except for brute force approach.

Each node from one set can be connected to any other node inside another set.

Any pointers to an (efficient) algorithm that solves this problem? Implementation is not required.

EDIT1

Here is one solution to the problem for n=7 :

Black dots are a set of nodes, and red dots are a set. Each black node must be connected to one red node so that the lines connecting them do not intersect.

EDIT2:

Further clarification: the positions of all nodes are fixed, and the resulting graph will have n edges. I also have no evidence that a solution exists, but I could not create an example where there was no solution. I am sure that somewhere there is evidence that the creation of such a planar schedule is always possible. In addition, only one solution is required, and not all possible solutions.

Answer 1

When a solution exists (see my comment, giving an example copy where it is absent), it can be found by finding the minimum weight match in a complete bipartite graph that contains a (red or black) vertex for each point, and for each red vertex u and of a black vertex v is an edge (u, v) of weight equal to the Euclidean distance between their corresponding points. This can be optimally solved over time O (V ^ 4).

Why does it work? The basic idea that I took from David Eisenstat, answering a similar question , is that whenever we have a pair of segments of the AB and CD lines that intersect at some point X, Trialgle Inequality can be used to show that the choice of any endpoint of each and their replacement gives a pair of line segments with a smaller or equal total length:

 A |\ | \ | \ X C---+-----D \ / \ / B AX + XC >= AC (tri. ineq.) BX + XD >= BD (tri. ineq.) AX + XC + BX + XD >= AC + BD (sum both sides) (AX + BX) + (XC + XD) >= AC + BD (rearrange LHS) AB + CD >= AC + BD (combine pairs of segments on LHS) 

Assuming further that the triangles AXC and BXC are non-degenerate, >= becomes a > . (A sufficient condition for this is that none of the three points containing at least 1 red and 1 black point is collinear.) Thus, for any given solution (assigning red nodes to black nodes), if this solution contains the intersection, then its total sum of the lengths of the line segments can be reduced by a nonzero amount by replacing the red (or black) endpoints of the two segments of the line of intersection.

In other words,

 Solution contains a crossing => sum of segment lengths is not minimal. 

Taking the opposite, we immediately get

 Sum of segment lengths is minimal => solution contains no crossing. 

Since the minimum weight matching algorithm returns the solution of the minimum possible weight, this establishes its correctness.

(Note that there is no need to worry about whether replacing the endpoints really ensures that the new pair of segments of the AC and BD line does not intersect - although it seems obvious that they will not, we all really need to prove the correctness is to show that crossing exists => sum not minimal .)