[問題] 圓的資料結構

作者: FRAXIS (喔喔)   2015-01-31 02:39:00
這是在研究所考題裡面看到的
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?
作者: FRAXIS (喔喔)   2015-02-12 23:35:00
我最後發現 這問題其實是在考power diagram..

Links booklink

Contact Us: admin [ a t ] ucptt.com