非交叉线段,同时最小化累积长度

Question

我想找到一个更好的算法来解决以下问题:

2D中有N个起点(紫色)和N个目标点(绿色).我想要一种算法,通过线段(棕色)将起始点连接到目标点,而没有任何这些段相交(红色),同时最小化所有段的累积长度.

我在C++中的第一个努力就是置换所有可能的状态,找到无交叉状态,以及总段长度最小为 O(n!)的状态.但我认为必须有更好的方法.

任何的想法？或者搜索好的关键词？

Answer 1

这是2D中的最小欧几里德匹配.该链接包含有关此问题的已知内容的参考书目.鉴于您希望最小化总长度,非交叉约束是多余的,因为交叉的任何一对段的长度可以通过将它们交叉来减少.