※ 引述《bleed1979 (十三)》之铭言： : 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 一条边的中垂线上任何一点，都与两个顶点距离相等， 三角形的外心则是三边中垂线的交点，同时也是外接圆的圆心， 自然和三角形顶点距离都相同。 跟 convex null 似乎倒是没什麽关系， 而且很容易可以找到一个反例， 想像一个 convex hull 中间密密麻麻塞满了点，只有中心位置有一块空白。 很明显这块空白就是最大圆，但他不会接触到任何 convex hull 上的点。 回到第一篇， Voronoi Diagram 的 edge 其实就是两个最近点间的中垂线"段"， 在这线段上任何一个位置当做圆心， 都可以画出一个圆使得两点落在圆周上，且圆内无其它点。 而 vertice 则是三条 edge 的交点，也就是三点的外心， 并且保证圆内也不会有其他点。 -- ◤ ◥ ◢ ◣ T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到问题，用SoftICE就对了！ ╰ ∕皿﹨ ◥皿◤ ╯ ◥█◤◢ ◥ ︶◤ Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.114.78.231