Non-intersecting line segments while minimizing the cumulative length

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.

Leave a Comment