※ 引述《tkcn (小安)》之铭言： : ※ 引述《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 上的点。 感谢您的回应， 然而，我的原文指的是convex hull任意不照顺序的三点所构成三角形， (我原文少讲了任意，造成你的误解真抱歉) 这个三角形的外心有可能落在你讲的中心位置。 其实这也是一个题目，SPOJ34或POJ1379。 原本我已实作出O(N^4)的代码，我用假设的方式， 将convex hull的所有点数当成"新的N"套入这个O(N^4)的算法。 再计算矩形4个角，矩形4个边的其中一个边上所有点，矩形中心点， 总共这麽多的运算，幸运地AC了。 关键应该是原本的N至多1000点，跑O(N^4)很慢。 但是我把convex hull的总点数来跑O(N^4)就很快了， 以上提供给需要解题的人。 : 回到第一篇， : Voronoi Diagram 的 edge 其实就是两个最近点间的中垂线"段"， : 在这线段上任何一个位置当做圆心， : 都可以画出一个圆使得两点落在圆周上，且圆内无其它点。 : 而 vertice 则是三条 edge 的交点，也就是三点的外心， : 并且保证圆内也不会有其他点。 结果我还是没有实作出O(NlogN)的算法，sigh... Bleed --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.43.115.241 ※ 编辑: bleed1979 来自: 114.43.115.241 (12/11 13:29)