Re: [問題] 圓的資料結構
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間9年前 (2015/01/31 09:56)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《FRAXIS (喔喔)》之銘言：
: 這是在研究所考題裡面看到的
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103418.pdf
: 給定 n 個半徑不完全相同的圓，要計算出總共有幾個連通的區域。
: 如果所有的圓是給定的，那可以用plane-sweep法解決。
: （不過我只能做到O((k + n) lg n)， k 是相交的圓的個數，不知道有沒有
: 跟 k 無關的方法）
: 但是另一個問題是要求 incremental 計算，這部份有什麼特殊的資料結構
: 或是演算法可以使用嗎？
: 雖然可以用KD-tree來儲存中心，但是這樣就忽略了半徑的資訊，有沒有什麼trick？
Check Ball Tree.
ftp://ftp.icsi.berkeley.edu/pub/techreports/1989/tr-89-063.pdf
There is an on-line construction algorithm in it.
--
一簫一劍平生意
負盡狂名十五年
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 75.142.52.228
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1422669370.A.E27.html
推
02/02 03:58, , 1F
02/02 03:58, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30