[问题] 圆的资料结构

楼主: 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