※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1422669370.A.E27.html