Non-intersecting line segments while minimizing the cumulative length

Question

I would like to find a better algorithm to solve the following problem:

There are N starting points (purple) and N target points (green) in 2D. I want an algorithm that connects starting points to target points by a line segment (brown) without any of these segments intersecting (red) and while minimizing the cumulative length of all segments.

My first effort in C++ was permuting all possible states, find intersection-free states, and among those the state with minimum total segment length O(n!) . But I think there has to be a better way.

Any idea? Or good keywords for search?

Answer 1

You can select a random connection, then each time delete one cross by changing the connections of its endpoints. This operation reduces the total length (by triangle inequality). Since the number of ways of lines crossing each other is finite, in a finite number of steps we arrive at a noncrossing solution. In practice, it should converge quickly.

Answer 2

Following qq3's answer which says the intersection constraint is redundant, there is just one more step. Assigning starting points to end points while minimizing total length. Fortunately there is a polynomial time algorithm for this:

Hungarian algorithm is a combinatorial optimization algorithm that solves the the assignment problem in polynomial time.

It reduces time order from O(n!) to O(n³).

Answer 3

This is Minimum Euclidean Matching in 2D. The link contains a bibliography of what's known about this problem. Given that you want to minimize the total length, the non-intersection constraint is redundant, as the length of any pair of segments that cross can be reduced by uncrossing them.

Answer 4

Looks like a you could use a BSP-type algorithm.