连接偶数个节点而不交叉 [英] Connect an even number of nodes without intersection
问题描述
我有两组n个节点。现在，我要连接一组中的每个节点与另一组中的另一个节点。生成的图形应该没有相交。
我知道几种扫掠线算法（
黑点是一组节点，红点是一组节点。每个黑节点都必须连接到一个红色节点，因此线
EDIT2：
进一步说明：所有节点的位置是固定的，结果图形将具有n条边。
我也没有任何证据表明存在解决方案，但是我无法创建没有解决方案的示例。我敢肯定某个地方有证明，总是可以创建这样的平面图。
此外，仅需要一个解决方案，而不是所有可能的解决方案。
何时存在解决方案（请参阅我的评论，给出一个不存在的示例实例），可以通过找到最小权重匹配在一个完整的二部图中，其中每个点都包含一个（红色或黑色）顶点，每个红色顶点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（两边加和）
（AX + BX）+（XC + XD）> = AC + BD（重新排列LHS）
AB + CD> = AC + BD（LHS上的段组合）
进一步假设三角形AXC和BXC不退化，则> = 成为> 。 （一个充分的条件是，没有包含至少1个红色和1个黑点的3个点的集合不是共线的。）因此，对于任何给定的解决方案（将红色节点分配给黑色节点），如果该解决方案包含交叉，则通过交换两个交叉线段的红色（或黑色）端点，可以将其线段长度的总和减少非零值。
换句话说，
解决方案包含交叉=>段长度的总和不是最小的。
采取相反的方法，我们立即得到
段长度的总和最小=>解决方案不包含交叉。
由于最小权重匹配算法返回了最小可能权重的解决方案，因此可以确定其正确性。
（注意，不必担心端点交换是否实际上保证了新的一对线段AC和BD不相交-虽然看起来显然他们不会，我们为证明正确性而实际需要的只是显示交叉存在=>总和不是最小的。）
I have two sets of n nodes. Now I want to connect each node from one set with another node from the other set. The resulting graph should have no intersections.
I know of several sweep line algorithms (Bentley-Ottmann-Algorithm to check where intersections occur, but I couldn't find an algorithm to solve those intersections, except for a brute-force approach.
Each node from one set can be connected to any other node within the other set.
Any pointers to (an efficient) algorithm that solves this problem? No implementation needed.
EDIT1:
Here is one solution to the problem for n=7:
The black dots are a set of nodes and the red dotes are a set. Each black node has to be connected to one red node so that the lines connecting them are not crossing.
EDIT2:
To further clarify: The positions of all the nodes are fixed and the resulting graph will have n edges. I also don't have any proof that a solution exists, but I couldn't create an example where there was no solution. I'm sure there is a proof out there somewhere that creating such a planar graph is always possible. Also, only one solution is needed, not all possible solutions.
When a solution exists (see my comment giving an example instance where it does not), it can be found by finding a minimum weight matching in a complete bipartite graph that contains a (red or black) vertex for every point, and for every red vertex u and black vertex v, an edge (u, v) of weight equal to the Euclidean distance between their corresponding points. This can be solved optimally in O(V^4) time.
Why should this work? The main idea, which I took from 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 can be used to show that picking either endpoint of each and swapping them gives a pair of line segments with lower or equal total length:
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)
Assuming further that the triangles AXC and BXC are non-degenerate, the >= becomes a >. (A sufficient condition for this is that no set of 3 points containing at least 1 red and 1 black point are collinear.) So, for any given solution (assignment of red nodes to black nodes), if that solution contains a crossing, then its total sum of line segment lengths can be reduced by a nonzero amount by swapping the red (or black) endpoints of the two crossing line segments.
In other words,
Solution contains a crossing => sum of segment lengths is not minimal.
Taking the contrapositive, we immediately get
Sum of segment lengths is minimal => solution contains no crossing.
Since the minimum weight matching algorithm returns a solution of minimum possible weight, this establishes its correctness.
(Notice that it's not necessary to worry about whether or not the endpoint-swapping actually guarantees that the new pair of line segments AC and BD don't intersect -- while it seems obvious that they won't, all we actually need for the proof of correctness is to show that crossing exists => sum not minimal.)
这篇关于连接偶数个节点而不交叉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
