masoud
masoud

Reputation: 56539

Non-intersecting line segments while minimizing the cumulative length

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?

Upvotes: 53

Views: 3016

Answers (4)

Saeed Amiri
Saeed Amiri

Reputation: 22565

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.

Upvotes: 3

masoud
masoud

Reputation: 56539

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

Upvotes: 1

qq3
qq3

Reputation: 386

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.

Upvotes: 37

Krumelur
Krumelur

Reputation: 32597

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

Upvotes: 1

Related Questions