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

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

看板Prob_Solve (計算數學 Problem Solving)作者seanwu (海恩)時間14年前 (2010/12/12 00:16)推噓1(1推 0噓 0→)

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

※ 引述《bleed1979 (十三)》之銘言： : ※ 引述《tkcn (小安)》之銘言： : : 一條邊的中垂線上任何一點，都與兩個頂點距離相等， : : 三角形的外心則是三邊中垂線的交點，同時也是外接圓的圓心， : : 自然和三角形頂點距離都相同。 : : 跟 convex null 似乎倒是沒什麼關係， : : 而且很容易可以找到一個反例， : : 想像一個 convex hull 中間密密麻麻塞滿了點，只有中心位置有一塊空白。 : : 很明顯這塊空白就是最大圓，但他不會接觸到任何 convex hull 上的點。 : 感謝您的回應， : 然而，我的原文指的是convex hull任意不照順序的三點所構成三角形， : (我原文少講了任意，造成你的誤解真抱歉) : 這個三角形的外心有可能落在你講的中心位置。呃不知道我有沒有誤會你的意思... 那例如底下的測資，4個點: (-4,-3) (4,-3) (0,5) (0,0) 那convex hull是前三個點，這也是唯一的三角形取法不過它的圓心在 (0,0) 這顯然不是最大空圓的圓心 : 其實這也是一個題目，SPOJ34或POJ1379。 : 原本我已實作出O(N^4)的代碼，我用假設的方式， : 將convex hull的所有點數當成"新的N"套入這個O(N^4)的算法。 : 再計算矩形4個角，矩形4個邊的其中一個邊上所有點，矩形中心點， : 總共這麼多的運算，幸運地AC了。 : 關鍵應該是原本的N至多1000點，跑O(N^4)很慢。 : 但是我把convex hull的總點數來跑O(N^4)就很快了， : 以上提供給需要解題的人。這題的測資大小，看起來是O(N^2lgN)就夠了方法是枚舉每個點p，求p對其它所有點連線段的中垂線的半平面交集 N條直線的半平面交可以O(NlgN)做完，而可能的LEC圓心則必在半平面交的頂點上 (其實這個就是Voronoi了，不過比較好做一點，當然時間複雜度也比較差一點) : : 回到第一篇， : : Voronoi Diagram 的 edge 其實就是兩個最近點間的中垂線"段"， : : 在這線段上任何一個位置當做圓心， : : 都可以畫出一個圓使得兩點落在圓周上，且圓內無其它點。 : : 而 vertice 則是三條 edge 的交點，也就是三點的外心， : : 並且保證圓內也不會有其他點。 : 結果我還是沒有實作出O(NlogN)的算法，sigh... 這個超級不好寫噢XDD 有興趣可以看一下這個 http://oistorer.blogspot.com/2006/08/2006_15.html 裡面有一篇《浅析平面Voronoi图的构造及应用》提到了做法和一些應用它用的是divide&conquer的方法，對於兩個不相交各N/2個點的triangulation 我們有(說來容易的)方法可以在O(N)的時間合併它們不過要真的寫到O(NlogN)的話就.. 有點不太健康 -- +1 ironwood branch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.137 ※ 編輯: seanwu 來自: 140.112.30.137 (12/12 00:17)