包围n个点的最小圆(100分)

  • 主题发起人 muyirenyan
  • 开始时间
本来写了一大堆，结果把自己写糊涂了，郁闷
现在大致说一下，
1，关于那个圆心的说法，因为我做出了一个粗略的对称图形。
若圆心不在交点处，则圆心到两端的距离必然一大一小，不会符

合条件的
2。关键就是画这个最小面积的多边型了，我要画对称图形的原

因是他的重心比较好找。
3，写上一段话的时候，考虑的是4个xy方向的凸点集的点阵
现在有点混，估计也说不清楚，我要好好考虑考虑
 
写完才发现楼主高兴中
若楼主成功解决此问题，拜托一定写出来解决方案！
 
to kidneyball:

收缩法的思想是先找一个能够容纳所有点的圆，当然，此圆不是最小的；然后逐步缩小此圆，同时满足包含所有点，直到无法收缩为止。此是得到的圆就是所求的最小圆。
 
其实可以进行次竞赛，看谁的算法优秀。

在20，000 X 20，000的平面内有随机均匀的有1，000，000个点，求包含所有点的最小圆，看谁的算法最快且正确。
 
新想了一下，应该是这样子的(渐进)
1、若这个圆轨迹上一个点也没有，则明显可以将该圆缩小至最小 包含一个点。
2、若圆轨迹上有一个点，即其他各个方向上都无交点，明显圆可向内包该点的方向移动，即可将圆心移动后再缩小该圆。
3、现在该圆轨迹上有两个点了，可分两种情况
1) 这两点为直径的端点...这样子的话结果可知
2) 这两点非直径端点，则该圆仍可向内包这两点的方向移动
这样的话可以得到一个轨迹上至少有3个凸包点的圆。
那么能不能找到比这个更小而符合条件的圆呢，答案是不
能，因为再小就盛不下这个三角形了。
综上所述，这样的圆必然符合这样一个条件
轨迹上若只有2个凸包集中的点，则这两点是直径端点。否则
至少包含凸包集中的3个点。而3个点是可以确定一个圆的。
嗯。现在问题好像简单多了哦。可以归结为这样一个问题
《判断点集的凸包集中距离最远的两点所确定的圆和凸包集中所
有3角形所确定的圆中哪一个能包含所有的点》
我再想想，大家也看看这里有谬误没有！
 
to lanyun2：
圆上有3个点依然可以收缩，只要这3个点在同一段劣弧上。
 
在这个问题里面，凸包的性质并没有太大不帮助。因为寻找凸包集合的计算本身就很大，应该是N的2次方，这已经大于找圆的计算量了，不划算。

to lanyun2：
你对收缩法的主要意思，但后面得到的结论却又明显错误。
 
to lanyun2：
你对收缩法的主要思想的理解是正确的，但后面得到的结论却又明显错误。
 
：（
果然错了，再想
 
不对不对,只要是3点在劣弧上就继续缩小圆.一直到不能缩小为止,这样找到的
最后一个圆仍然符合我所说的条件:
" 轨迹上若只有2个凸包集中的点，则这两点是直径端点。否则
至少包含凸包集中的3个点。而3个点是可以确定一个圆的。"
所以沙老大,我的结论是正确的
 
to lanyun2:

“2) 这两点非直径端点，则该圆仍可向内包这两点的方向移动
这样的话可以得到一个轨迹上至少有3个凸包点的圆。
那么能不能找到比这个更小而符合条件的圆呢，答案是不
能，因为再小就盛不下这个三角形了。”
你这段话显然是有错的。

“可以归结为这样一个问题
《判断点集的凸包集中距离最远的两点所确定的圆和凸包集中所
有3角形所确定的圆中哪一个能包含所有的点》”
这句话也是错误的。
 
用收缩法可以较快的找出最小圆来；现在我感兴趣的是有没有更快的方法，通过进行N的线性次计算得到最小圆。
 
把creation-zy提到的论文的算法和证明部分抄录如下, 版权是原作者的, 希望方舟子不要来打我假.....

以下部分摘录自:汪卫，王文平，汪嘉业，求一个包含点集所有点的最小圆的算法，软件学报，2000，11（9）：1237-1240
=================================================================
求一个最小圆包含给定点集所有点的问题是人们在实践和理论上都十分感兴趣的一个问题.由于这个圆的圆心是到点集中最远点最近的一个点,因而在规划某些设施时很有实用价值.这个圆心也可看成是点集的中心.此外,在图形学中,圆也常可取作边界盒,使用它可减少很多不必要的计算.在空间数据库中可将该问题用于建立空间数据的索引以提高查询速度[1,2].这个问题看起来十分简单,但用直观的算法去解此问题,其复杂性可达O(n4),其中n为点集中点的数目.有关此问题的讨论在计算几何的专著及论文中未见报道[3～5].本文提出了一种新的算法并证明了这种算法的时间复杂性为O(|lg(d/R)|*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆周最近的点到圆周的距离.1

　算　法
第1步.在点集中任取3点A,B,C.

第2步.作一个包含A,B,C三点的最小圆.圆周可能通过这3点(如图1所示),也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端.

第3步.在点集中找出距离第2步所建圆圆心最远的点D.若D点已在圆内或圆周上,则该圆即为所求的圆,算法结束.否则,执行第4步.

第4步.在A,B,C,D中选3个点,使由它们生成的一个包含这4点的圆为最小.这3点成为新的A,B和C,返回执行第2步.

若在第4步生成的圆的圆周只通过A,B,C,D中的两点,则圆周上的两点取成新的A和B,从另两点中任取一点作为新的C.

2　算法正确性
本节要证明上述算法一定能终止,且最后一次求得的圆即是所要求的包含点集所有点的最小圆.

引理1.算法第4步所生成的圆的半径随着迭代过程递增.
证明:因为第4步每一次生成的圆是包含原来的A,B,C三点,又要加上圆外的一点,而上一次生成的圆是包含A,B,C的最小圆,因而新圆的半径一定比原来的圆半径要大.

定理1.上述算法是收敛的,且最后得到包含点集所有点的最小圆.
证明:因为在点集中任取3点或两点生成的包含这3点或两点的最小圆的个数是有限的.由引理1可知,算法进行过程中所生成的圆的半径是递增的,因而经过有限次迭代后,可求得这些最小圆中半径最大的一个.从算法第3步可知,只有当点集中所有点都在由3个点或两个点生成的最小圆内时,算法才结束,因而最后得到的圆一定是包含点集中所有点的最小圆.
 
to 沙隆巴斯的主人
请问能详细说说收缩法的步骤吗。你的想法的关键是“然后逐步缩小此圆，同时满足包含所有点，直到无法收缩为止。”。在一个连续平面，在圆心位置与半径都不确定的情况下，如何收缩？具体点说，假如一开始你把无限远位置定为圆心，如何收缩到一个能包括所有点的位置？在这之后，又以什么算法来收缩？
 
to kidneyball：
我的算法是这样的
1：任取一点X，找到离X最远的一点A（如果有多个点同时离X最远，那么任取一点）；
2：找到离A最远的一点B（如果有多个点同时离A最远，那么任取一点）；
3：A-B的中点为O，找到距离O最远的点C（如果有多个点同时离O最远，那么任取一点）；
4：以O为圆心，O-C为半径做圆；（此圆必定包含所有点）；
5：判定此圆是否可以缩小，若不可缩小，则此圆为所求之最小圆，结束；
6：按照一定路径移动圆心，缩小圆；
7：判定圆是否包含所有点，若是：回到5；若否：继续；
8：按照一定路径移动圆心，放大圆；回到7；
 
算法的第6、7、8步做点修改
6：按照一定路径移动圆心，缩小圆，半径的缩小量为q；
7：判定圆是否包含所有点，若是：q=3/4q,回到5；若否：继续；
8：返回到最近一次得到包含所有点的圆的状态，另q=q/2，返回7；
 
关于判定圆是否可以继续缩小，按照以下方法。
1、若圆周上仅一点，必然可以缩小；
2、若圆周上仅两点，且两点连线不为直径，可以缩小；
3、若圆周上有多于两点，但包含所有点的弧为劣弧，可以缩小；

关于“按照一定路径移动圆心，缩小圆”，按照以下方法：
1、若圆周上仅有1点，设点为A，圆心为O，新圆心为O'沿O-A向A靠拢，半径
为原半径-q，做过A的圆；
2、若圆周上仅有2点，设为点A和B，原点为O，则原点O必在A-B连线的中垂线上。现
在将O点沿A-B连线的中垂线向A-B靠拢到O'，半径为原半径-q，做圆。
3、若圆周上有多于2点，且包含所有点的弧为劣弧，则取劣弧的两个端点为A、B，按照
前面的第2种情况进行处理。
 
to 沙隆巴斯的主人
我觉得这个算法有点问题。
首先， “6：按照一定路径移动圆心，缩小圆；”如何确定路径是个问题。如果圆心移动方向不正确，半径是不可能收敛到最小的。当然，移动量也是一个问题。

其次，如何判断“判定此圆是否可以缩小，若不可缩小”，特别是在圆心未定的情况下。

第三，每一次 “判定圆是否包含所有点，若是：回到5；若否：继续；”就是N次的求两点距离与比较。
而按你所说的缩小策略半径，显然当Q是有理数的情况下，绝不可能算出无理数来。因此理论上任何一个以无理数为坐标的点就会令你的算法陷入死循环。当然实际上，受精度限制，但因而这个算法的复杂度也严重受精度影响。
而即使不考虑无理数的问题，也无法确定这个算法会在多少步内完成（显然步数与N无关，而与点的位置、圆心的位置、半径和缩小量，还有没提到的圆心移动量有关）。或者可以这样说，在精度足够的情况下，任意给出自然数n, 都有可能存在一个点，令这个算法的迭代次数超过n。
 
to kidneyball：
你说的第一和第二点，在前面的补充说明里面已经有了阐述。

对于第三点，应该认为能够在计算机里表示的数值都是有限位精度的。算法里面是用2分法来逼近，这是个非常快的方法，它按照对数收敛，非常有限步就可以逼近到足够精度，从而找到解。

另外，q没有设初值，这是个疏漏，应该为1/4半径。
而且“ 7：判定圆是否包含所有点，若是：q=3/4q,回到5；若否：继续；”也有错误，
应该改为“ 7：判定圆是否包含所有点，若是：q=1/4q,回到5；若否：继续；”
 
1 证明“这样的圆轨迹上若只有2个凸包集中的点，则这两点是

直径端点。否则至少包含凸包集中的3个点”这句话的正确性
1)只有两个点的话，那么若非直径，则这个圆不是最小的
2)由1)得知，只要圆上只有非直径端点的两个点，则最少有一
个更小的圆可以覆盖所有点。一直到轨迹上最少有三个或以
上的点为止。
命题得证！
2 求最小圆的算法
1、取任2点，在过这两点的直线两侧分别找到距离这条直线最
大的两个点A，B(必为凸点，证明就略啦)，以AB为直径做
圆 (时间复杂度n)
2、找到距离圆心最远的点c(复杂度n)
3、判断最远的点是否在圆内，是则结束算法，否则转4(复杂
度1)
4、做包含A，B，C三点的最小圆，转2(复杂度不会算:(
注：包含三角形的最小圆，若是锐角三角形，则是外接圆
若是钝角三角形，则是以三角形最长边为直径的三角形
 
您必须登录或注册才可回复。

Similar threads

不
奇淫怪巧之给Delphi的PrintDialog增加一个页码选定范围打印的Edit - 不得闲
回复
0
查看
707
不得闲
不
S
[教程]ZAsync 异步编程之四：请记住匿名函数是一个接口
回复
0
查看
578
swish
S
不
关于Delphi的子类化控件消息淫荡法则之一 - 不得闲
回复
0
查看
551
不得闲
不
不
Delphi中设置条件断点 - 不得闲
回复
0
查看
651
不得闲
不
S
[教程]IZAsyncInvoker 异步编程之三：我们对异步编程的一些观点
回复
0
查看
576
swish
S
顶部