PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] Largest Empty Circle(LEC) Problem

看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間14年前 (2010/12/11 12:42)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/5 (看更多)

※ 引述《bleed1979 (十三)》之銘言： : 2010/12/11 首po : 想請教Largest Empty Circle(LEC) Problem在O(NlogN)算法的實作步驟。 : 何謂LEC Problem？ : 平面上一個矩形區域裡有N個點。 : 找區域裡的一個最大圓，圓內不得包含任意一個點(圓邊上可以)。 : 目前的努力： : 因為是最大圓，所以圓一定要擴張到和某些點接觸，如此才可稱最大。 : 這個問題的O(N^4)解法為取任意3點計算外心(circumcenter)， : 外心定義是三角形三個邊中垂線交點，所求最大圓的圓心必為其中一個外心。 : 因為取任意3點，得有O(N^3)的時間，把這個點和N個點做距離測量O(N)， : 留下距離最遠的，所以合計是O(N^4)。這個已經實作出來。 : O(NlogN)的解法運用Voronoi Diagram Algorithm， : 但我找不到一個合理且清楚的描述或解法。 : 故想請教版友對這個LEC問題求解的想法，謝謝。 : Bleed : ============================================================= : 2010/12/11 第2篇 : 想請教最大圓的圓心是否為convex hull的其中三個點所構成三角形的外心呢？ : 因為我找到一篇關於Voronoi Diagram的論文， : 文中的做法是對convex hull上的點作運算的。 : 持續努力中，有結果再回報。 : Bleed 一條邊的中垂線上任何一點，都與兩個頂點距離相等，三角形的外心則是三邊中垂線的交點，同時也是外接圓的圓心，自然和三角形頂點距離都相同。跟 convex null 似乎倒是沒什麼關係，而且很容易可以找到一個反例，想像一個 convex hull 中間密密麻麻塞滿了點，只有中心位置有一塊空白。很明顯這塊空白就是最大圓，但他不會接觸到任何 convex hull 上的點。回到第一篇， Voronoi Diagram 的 edge 其實就是兩個最近點間的中垂線"段"，在這線段上任何一個位置當做圓心，都可以畫出一個圓使得兩點落在圓周上，且圓內無其它點。而 vertice 則是三條 edge 的交點，也就是三點的外心，並且保證圓內也不會有其他點。 -- ◤ ◥ ◢ ◣ T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！ ╰ ∕皿﹨ ◥皿◤ ╯ ◥█◤◢ ◥ ︶◤ Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.231