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

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

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/12/11 13:26)推噓0(0推 0噓 0→)

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

※ 引述《tkcn (小安)》之銘言： : ※ 引述《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 上的點。感謝您的回應，然而，我的原文指的是convex hull任意不照順序的三點所構成三角形， (我原文少講了任意，造成你的誤解真抱歉) 這個三角形的外心有可能落在你講的中心位置。其實這也是一個題目，SPOJ34或POJ1379。原本我已實作出O(N^4)的代碼，我用假設的方式，將convex hull的所有點數當成"新的N"套入這個O(N^4)的算法。再計算矩形4個角，矩形4個邊的其中一個邊上所有點，矩形中心點，總共這麼多的運算，幸運地AC了。關鍵應該是原本的N至多1000點，跑O(N^4)很慢。但是我把convex hull的總點數來跑O(N^4)就很快了，以上提供給需要解題的人。 : 回到第一篇， : Voronoi Diagram 的 edge 其實就是兩個最近點間的中垂線"段"， : 在這線段上任何一個位置當做圓心， : 都可以畫出一個圓使得兩點落在圓周上，且圓內無其它點。 : 而 vertice 則是三條 edge 的交點，也就是三點的外心， : 並且保證圓內也不會有其他點。結果我還是沒有實作出O(NlogN)的算法，sigh... Bleed -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.115.241 ※ 編輯: bleed1979 來自: 114.43.115.241 (12/11 13:29)