Non-intersecting line segments while minimizing the cumulative length

53
votes

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.

enter image description here

Any idea? Or good keywords for search?

4
c++performancealgorithmgeometry
Maybe some type of topological sort? – Kerrek SB
I don't know the answer either but I would create any solution (ignoring conflicts) and then resolve conflict individually: when two lines conflict, it seems that switching one pair of end points resolves the conflict. I'm not sure how to guarantee progress, though. – Dietmar Kühl
@DietmarKühl: Switching endpoints could cause a different conflict to appear. – Oliver Charlesworth
@OliCharlesworth: yes, I realize this. That is the part about guaranteeing progress: it won't work if things are resolved in a form creating a cycle. – Dietmar Kühl
@Masoud M: Up to how many point-pairs do you expect to handle? – RBarryYoung

4 Answers

38
votes

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.

3
votes

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.

1
votes

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

1
votes

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(n3).