將平衡樹映射到平面上的點

Question

我們得到一棵大小爲N的平衡樹，意思是對於樹中的每個節點，如果以該節點爲根的子樹的大小爲n和k，則其k個子樹的大小爲Omega(n/k)。我們還在飛機上給出了N點，沒有三個是共線的。我們試圖在樹中的節點之間找到一個雙射點，並在平面上指向，以便在平面上繪製樹不會導致任何邊緣交叉。 k是Theta(1)，並且可以是不同的每個節點。

我試圖找到解決這個遞歸的解決方案，但都無濟於事，因爲我不知道怎麼才能保證無交叉的要求。目標運行時是O(n log^2 n)，所以形式T(n)=k*T(n/k) + O(n log n)復發將導致這一點，所以我想沿着這些線路的想法。我要通過x-coord對點進行排序，找到中值，然後將其餘點分成塊並遞歸求解。但是我已經繪製出讓解決方案失敗的測試用例。任何幫助？

Answer 1

您應該能夠選擇適合自己的根的任意一點，然後切片了飛機周圍像一個餡餅，使得每個區域包含在其相應的子樹點的數量，並從根本上線到該地區的任何一點都完全在該地區內。

然後，你應該能夠做同樣的遞歸，與每一個子區域。隨着每一個子樹，則需要在周圍的子樹的根，這應該給你T(n) = k*T(n/k) + O(n log n)復發的角度以便在該子區域內的剩餘點重新排序。

---

編輯：關於進一步的想法，你可能不會選擇任意一點;你想在你的點的凸包上選擇一個點，這樣入射線不會與凸包相交 - 否則，你的子樹可能會穿過入線。這很容易通過挑選當前角度排序中的子集的第一個元素來完成。