雙邊連接邊界列表

給定DCEL，我如何找到最接近的一對網站？雙邊連接邊界列表

說給定的DCEL是一個Voronoi圖，我如何找到最接近的一對網站？時間複雜度是多少？

來源

2012-09-24 Aakash Anuj

最簡單的方法是遍歷所有邊，找到它們相鄰的面，計算Voronoi中心之間的距離，並返回最小的一對。如果您的DCEL實現無法直接在邊上進行迭代，則可以使用任何圖遍歷算法（深度優先，寬度優先等）進行迭代。

無論如何，時間複雜度與輸入數據結構的大小成正比。

來源

2012-09-24 19:56:06 comingstorm

但是，如何獲得Voronoi圖中的網站？ voronoi圖僅包含esges和VD的頂點> –

如果DCEL用於Voronoi圖（如您的問題），則應將站點信息附加到面上。如果您再沒有網站信息，您就會遇到問題 - 您是在問如何從Voronoi頂點重建原始網站？ – comingstorm

另一種說法是：DCEL中的每個半邊通常同時具有面對它的face的指針和指向其頂點的origin指針（以及指向edge的next和twin指針）。如果你可以控制你的DCEL結構，並且它沒有'face'指針，那麼添加一個。但是如果你從某個圖書館得到的沃羅諾依圖沒有任何臉部數據，可以原諒你問「爲什麼不？」。 – comingstorm

雙邊連接邊界列表

回答

相關問題