[請益] Largest Empty Circle(LEC) Problem
看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/12/11 07:49)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/5 (看更多)
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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.115.241
※ 編輯: bleed1979 來自: 114.43.115.241 (12/11 08:18)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 5 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
