荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: huhaiming (一生只爱她), 信区: Program
标  题: 求最小圆的方法
发信站: 荔园晨风BBS站 (Sun Apr  6 17:19:21 2003), 站内信件

一些省略的部分可以参看
http://www.chinaschool.org/aosai/lwjl/02-0626.htm

[问题]
  给定一些点,求最小的球,使那些点都在球内或球上。

[分析]
  先考虑平面的情形:给定n个点的集合P,记md(P)为最小半径的圆,使P不再球
的外部。我们约定,P=时md(P)=;P={p}时md(P)=p。可以很容易的看出,md(P)是
唯一的。
  md(P)可以由在边界上的至多3个点确定,这就是说,存在P的一个子集S在
md(P)的边界上,使得|S|≤3且md(S)=md(P);所以如果pS,则md(P-{p})=md(P),
或等价的,如果md(P-{p})md(P),那么pS,于是p在md(P)的边界上。这将导出我们
的算法。

  我们从一个空集开始,然后不断的把P中的点加入,同时维护最小的圆。令,
假设我们已经计算了,如果,那么D对于i+1个点仍然是最小的圆;否则,一定要在
的边界上,我们在计算D'时,调用一个过程b_mindisk(A,p),即计算最小的圆且在
边界上。

  总过程如下:



  下面要解决计算b_mindisk(A,p)的问题。
  为此,我们设P和R是平面上的有限点集,b_md(P,R)是包含P的最小球且使R在
它的边界上。明显的,b_md(P, )=md(P),且b_md(P,R)可能不存在如果R非空。

  可以证明:

  P和R是平面上的有限点集,P非空,p是P中的一点
  1. 如果存在包含P的圆且以R为它的边界,那么b_md(P,R)是有定义的(唯一的
)。
  2. 如果pb_md(P-{p},R),那么p在b_md(P,R)的边界上,也就是,
    b_md(P,R)=b_md(P-{p},Rp)
  3. 如果b_md(P,R)存在,则有一个集合S,至多有P中的max{0,3-|R|}个元素,
使得
    b_md(P,R)=b_md(S,R)。

  于是,我们改写b_mindisk为b_mindisk(P,R)用来返回b_md(P,R):




  下面,我们将把P视作一个序列,这样我们可以进一步的改进算法。先修改
b_mindisk的else部分如下:



  下面是一个关键的改进。
  在上面的程序中,我们要选取排列。什么样的排列是一个较好的排列呢?当然
,就是这个排列的前面几个点确定了问题的解,这样,我们可以省去很多的递归。
这是理想情况,但是我们要尽量使确定解的点靠近序列的前部。于是,我们在计算
的过程中,将我们认为的重要的点移动到序列的最前部。

  于是,上面的程序我们改写成:



  这个方法在高维的时候十分有效。本题是3维的情形。



--

菩提本无树,明镜亦非台

本来无一物,何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店