8

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

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

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

任何指向解决此问题的（有效）算法的指针？无需实施。

编辑1：

这是解决问题的一种方法n=7：

路口问题

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

编辑2：

进一步澄清：所有节点的位置都是固定的，结果图将有 n 条边。我也没有任何证据证明存在解决方案，但我无法创建没有解决方案的示例。我敢肯定，某处有证据表明始终可以创建这样的平面图。此外，只需要一种解决方案，而不是所有可能的解决方案。

4

1 回答 1

7

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

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

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 不相交——虽然很明显它们不会相交，但我们真正需要的只是正确性的证明是证明crossing exists => sum not minimal.)

于 2016-06-29T14:35:25.797 回答