algorithm - 连接偶数个无交点的节点

Question

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

我知道有几种扫描线算法(Bentley-Ottmann-Algorithm 可以检查交点出现的位置，但我找不到解决这些交点的算法，除了蛮力方法。

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

任何指向解决此问题的(有效)算法的指针？无需实现。

编辑1:

这是 n=7 问题的一种解决方案:

黑点是一组节点，红点是一组。每个黑色节点必须连接到一个红色节点，这样连接它们的线就不会交叉。

编辑 2:

进一步说明:所有节点的位置都是固定的，生成的图将有 n 条边。我也没有任何解决方案存在的证据，但我无法创建一个没有解决方案的示例。我确信在某个地方有证据表明创建这样的平面图总是可能的。此外，只需要一个解决方案，而不是所有可能的解决方案。

Answer 1

当解决方案存在时(参见我的评论，给出了一个不存在的示例实例)，可以通过查找 minimum weight matching 找到它。在一个完整的二分图中，每个点都包含一个(红色或黑色)顶点，对于每个红色顶点 u 和黑色顶点 v，边(u，v)的权重等于它们对应点之间的欧氏距离。这可以在 O(V^4) 时间内得到最佳解决。

为什么要这样做？主要思想，我从David Eisenstat's answer to a similar question ，是每当我们有一对线段 AB 和 CD 在某个点 X 相交时，Triangle Inequality可用于显示选择每个端点并交换它们会得到一对总长度小于或等于总长度的线段:

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 是非退化的，则 >= 变为 >。 (一个充分条件是没有包含至少 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 不相交——虽然看起来很明显它们不会相交，但我们实际上正确性证明的需要是证明存在交叉 => 总和不是最小值。)