Disjoint line segments while minimizing cumulative length

Question

I would like to find the best algorithm to solve the following problem:

In 2D, there are N starting points (purple) and N target points (green). I want an algorithm that connects the source points to the target points with a segment (brown), without any of these segments intersecting (red) and minimizing the cumulative length of all segments.

My first attempt in C ++ was to rearrange all possible states, search for states that are free from intersections, and among those that have a minimum total segment length of O (n!). But I think there should be a better way.

Any idea? Or good search keywords?

Answer 1

This is the Minimum Euclidean match in 2D . The link contains a bibliography of what is known about this issue. Given that you want to minimize the total length, the non-intersection constraint is redundant, since the length of any pair of segments that intersect can be reduced by intersecting them.

Answer 2

You can choose a random connection, then delete one cross each time (actually change the connection of your endpoints). This algorithm works and ends with the final steps. maybe you say that switching crosses causes a new cross, regardless of whether you are going to minimize the total length of your answer each time you switch one cross, and this path cannot be infinite (since the total length of the lines is finite). Actually works in O (F * n ^ 2), where F= sum of all line segments * power of 10 (to make it integer). This O is very optimistic, I think that if you try this simple algorithm, it will work fine. Of course, this is better than brute force in general.

Answer 3

It looks like you could use a BSP-type algorithm.

Answer 4

Use this algorithm with order O (n ³ ):

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

How can this help? Well, he will only find the minimum cumulative length. But...

WHEN THE TOTAL LENGTH IS MINIMUM, NO INTERSECTION.

So, since @ qq3 says that the intersection restriction is redundant, and after removing this restriction, it can reduce the order from O (n!) To O (n ³ ).