连接偶数个无交点的节点
Connect an even number of nodes without intersection
我有两组 n 个节点。现在我想将一组中的每个节点与另一组中的另一个节点连接起来。结果图应该没有交点。
我知道几种扫掠线算法（Bentley-Ottmann-Algorithm 用于检查交点出现的位置，但我找不到解决这些交点的算法，除了蛮力方法。
一组中的每个节点都可以连接到另一组中的任何其他节点。
任何指向解决此问题的（有效）算法的指针？无需实施。
EDIT1:
这是 n=7 问题的一种解决方案：
黑点是一组节点，红点是一组。每个黑色节点必须连接到一个红色节点，这样连接它们的线就不会交叉。
EDIT2:
进一步说明：所有节点的位置都是固定的，生成的图将有n条边。
我也没有任何解决方案存在的证据，但我无法创建一个没有解决方案的示例。我确信在某个地方有证据表明创建这样的平面图总是可能的。
此外，只需要一个个解决方案，而不是所有可能的解决方案。
当解决方案存在时（参见我的评论给出了一个不存在的示例实例），可以通过在包含（红色或黑色）顶点的完整二分图中找到 minimum weight matching每个点，对于每个红色顶点 u 和黑色顶点 v，边 (u, v) 的权重等于它们对应点之间的欧氏距离。这可以在 O(V^4) 时间内得到最佳解决。
为什么要这样做？我从 David Eisenstat's answer to a similar question, is that whenever we have a pair of line segments AB and CD that intersect at some point X, the 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.
由于最小权重匹配算法 returns 是最小可能权重的解决方案，因此确定了其正确性。
（请注意，不必担心端点交换是否真的保证新的一对线段 AC 和 BD 不相交——虽然很明显它们不会相交，所有我们实际上需要的正确性证明是证明 crossing exists => sum not minimal.)
我有两组 n 个节点。现在我想将一组中的每个节点与另一组中的另一个节点连接起来。结果图应该没有交点。
我知道几种扫掠线算法（Bentley-Ottmann-Algorithm 用于检查交点出现的位置，但我找不到解决这些交点的算法，除了蛮力方法。
一组中的每个节点都可以连接到另一组中的任何其他节点。
任何指向解决此问题的（有效）算法的指针？无需实施。
EDIT1:
这是 n=7 问题的一种解决方案：
黑点是一组节点，红点是一组。每个黑色节点必须连接到一个红色节点，这样连接它们的线就不会交叉。
EDIT2:
进一步说明：所有节点的位置都是固定的，生成的图将有n条边。 我也没有任何解决方案存在的证据，但我无法创建一个没有解决方案的示例。我确信在某个地方有证据表明创建这样的平面图总是可能的。 此外，只需要一个个解决方案，而不是所有可能的解决方案。
当解决方案存在时（参见我的评论给出了一个不存在的示例实例），可以通过在包含（红色或黑色）顶点的完整二分图中找到 minimum weight matching每个点，对于每个红色顶点 u 和黑色顶点 v，边 (u, v) 的权重等于它们对应点之间的欧氏距离。这可以在 O(V^4) 时间内得到最佳解决。
为什么要这样做？我从 David Eisenstat's answer to a similar question, is that whenever we have a pair of line segments AB and CD that intersect at some point X, the 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.
由于最小权重匹配算法 returns 是最小可能权重的解决方案，因此确定了其正确性。
（请注意，不必担心端点交换是否真的保证新的一对线段 AC 和 BD 不相交——虽然很明显它们不会相交，所有我们实际上需要的正确性证明是证明 crossing exists => sum not minimal.)