作者bleed1979 (十三)
站内Prob_Solve
标题[请益] Largest Empty Circle(LEC) Problem
时间Sat Dec 11 07:49:40 2010
2010/12/11 首po
想请教Largest Empty Circle(LEC) Problem在O(NlogN)算法的实作步骤。
何谓LEC Problem？
平面上一个矩形区域里有N个点。
找区域里的一个最大圆，圆内不得包含任意一个点(圆边上可以)。
目前的努力：
因为是最大圆，所以圆一定要扩张到和某些点接触，如此才可称最大。
这个问题的O(N^4)解法为取任意3点计算外心(circumcenter)，
外心定义是三角形三个边中垂线交点，所求最大圆的圆心必为其中一个外心。
因为取任意3点，得有O(N^3)的时间，把这个点和N个点做距离测量O(N)，
留下距离最远的，所以合计是O(N^4)。这个已经实作出来。
O(NlogN)的解法运用Voronoi Diagram Algorithm，
但我找不到一个合理且清楚的描述或解法。
故想请教版友对这个LEC问题求解的想法，谢谢。
Bleed
=============================================================
2010/12/11 第2篇
想请教最大圆的圆心是否为convex hull的其中三个点所构成三角形的外心呢？
因为我找到一篇关於Voronoi Diagram的论文，
文中的做法是对convex hull上的点作运算的。
持续努力中，有结果再回报。
Bleed
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.115.241
※ 编辑: bleed1979 来自: 114.43.115.241 (12/11 08:18)