連接偶數個無節點的節點

我有兩組n個節點。現在我想將一個集合中的每個節點與另一個集合中的另一個節點連接起來。結果圖應該沒有交點。連接偶數個無節點的節點

我知道的幾種掃描線算法（Bentley-Ottmann-Algorithm以檢查交叉口發生，但我無法找到一個算法來解決這些路口，除了蠻力的方法。

從一組每個節點都可以被連接到任何其它節點的另一組內

任何指針（一種有效的）算法，解決了這個問題沒有所需的實施

EDIT1：？

這裏是一個解決問題的方法爲n=7：

中的黑點是一組節點和所述紅色寵愛是一組。每個黑色節點必須連接到一個紅色節點，以便連接它們的線路不會交叉。

EDIT2：

爲了進一步闡明：所有節點的位置是固定的，所得到的曲線圖將具有n條邊。我也沒有證據表明存在解決方案，但我無法創建一個沒有解決方案的例子。我確信有一個證據表明，創建這樣的平面圖總是可能的。此外，只有一個解決方案是必要的，並非所有可能的解決方案。

來源

2016-06-29 Soift

這是一個沒有解決方案的問題實例：繪製任何長度爲4的線段。在左端（或底端）放置一個紅點，並在另一個紅點沿着這條線向右（或向上）1單位。在右邊（或頂部）放一個黑點，然後從那裏向左（或向下）放一個黑點1單位。即該圖看起來像「R R B B」。所有可能的黑紅線對在長度爲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 + BC (rearrange LHS) 
    AB  + CD  >= AC + BC (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和BC不相交 - 雖然看起來很明顯他們不會，但我們所有人實際上需要證明的正確性是表明crossing exists => sum not minimal。）

來源

2016-06-29 14:35:25

「沒有必要擔心端點交換是否實際上保證新的線段對AC和BC不相交」 - 「AD」我假設。但是，如果它們在改變它們的末端之後相交，則再次改變它們將導致AB和CD，其長度的總和大於AD和BC的總和，這是不可能的。因此它們不相交。 – Vesper

連接偶數個無節點的節點

回答

相關問題