无交叉地连接偶数个节点

Question

我有两组n个节点.现在我想将一组中的每个节点与另一组中的另一个节点连接起来.结果图应该没有交叉点.

我知道几种扫描线算法(Bentley-Ottmann-Algorithm来检查交叉点发生的位置,但除了蛮力方法之外,我找不到解决这些交叉点的​​算法.

一组中的每个节点可以连接到另一组中的任何其他节点.

任何解决这个问题的(一种有效的)算法的指针？无需实施.

编辑1:

以下是该问题的一种解决方案n=7:

黑点是一组节点,红点是一组.每个黑色节点必须连接到一个红色节点,以便连接它们的线不交叉.

EDIT2:

为了进一步说明:所有节点的位置都是固定的,结果图将有n个边.我也没有任何证据证明存在解决方案,但我无法创建一个没有解决方案的例子.我确信在那里有一个证据可以创建这样一个平面图.此外,只需要一种解决方案,而不是所有可能的解决方案.

Answer 1

当存在一个解决方案时(参见我的评论给出一个不存在的示例实例),可以通过在完整的二分图中找到最小权重匹配来找到它,该二分图包含每个点的(红色或黑色)顶点,以及每个红色顶点u和黑色顶点v,边缘(u,v)的权重等于它们对应点之间的欧几里德距离.这可以在O(V ^ 4)时间内最佳地解决.

为什么要这样做？我从David Eisenstat对类似问题的答案中得出的主要思想是,每当我们有一对线段AB和CD在某点X相交时,三角不等式可以用来表示选择每个点的任一端点并交换它们给出一对总长度较小或相等的线段:

A
|\
| \
|  \ X
C---+-----D
     \   /
      \ /
       B

AX + XC >= AC (tri. ineq.)
BX + XD >= BD (tri. ineq.)
AX + XC + BX + XD >= AC + BD (sum both sides)
(AX + BX) + (XC + XD) >= AC + BD (rearrange LHS)
   AB     +    CD     >= AC + BD (combine pairs of segments on LHS)

进一步假设三角形AXC和BXC是非简并的,则>=变为a >.(对此的充分条件是没有包含至少1个红色和1个黑色点的3个点的集合是共线的.)因此,对于任何给定的解决方案(将红色节点分配给黑色节点),如果该解决方案包含交叉点,则通过交换两个交叉线段的红色(或黑色)端点,可以将线段长度的总和减少非零量.

换一种说法,

Solution contains a crossing => sum of segment lengths is not minimal.

采取相反的立场,我们立即得到

Sum of segment lengths is minimal => solution contains no crossing.

由于最小权重匹配算法返回最小可能权重的解,因此确定了其正确性.

(请注意,没有必要担心端点交换是否实际上保证新的线段AC和BD不相交 - 虽然很明显他们不会,但我们实际需要的只是正确性的证明就是证明这一点crossing exists => sum not minimal.)