平面n个点的最小包围圆必过该点集中距一个外接矩形中心最远的点

aimisiyou

看来是找不到这么一个点了！（它由系统内部确定，满足到该点最远的点同时也在点集最小包围圆上。）如果能找到，那么很容易推出求解最小包围圆的复杂度为\(O(n)\)!

aimisiyou

似乎找到了这个点。就是点集外接矩形中心到点集拟合直线的垂足点。

aimisiyou

这个有反例么？

zhouguang

楼主的目标或许是找到一种实用算法：已知给定的n个点，求一个最小圆，包含这n个点。
如果如斯，那么或许可以这样算：
1、求出最上、最下、最左、最右的四个点，然后求包含这4个点的最小圆。假定此步复杂度O(1)，呵呵；
2、选择某一个圆外的点A，比如说距离圆心最远的点，找一个更大的圆，要求同时满足3条：圆包含A、此圆最小、已经在圆内的点原则上不能出去；
3、goto 2；
讨论一下第2步的复杂度：
如果要求已经在圆内的点（含边界）不能出去，那么比较麻烦，先不说这个；
如果要求已经在边界上的点不能出去，容许在原先在圆内的点出去，那么就简单了，就先这么干，如此假定此步复杂度O(1)，呵呵。

可以看到，随着循环的进行，圆内的点的数目不一定单调递增，但是圆的面积却单调递增了。实际上，圆面积递增的次数是有限的。

备注：为什么“假定此步复杂度O(1)”？因为求出最上面的点或距离圆心最远的点本身的复杂度就O(n)了，呵呵。

我们或许挑战这样一个问题：
构造平面上包含n个点的点集，并且指定其中3点。
计算此3点的最小包含圆c0，找到距离最小包含圆圆心c0的最远的点A（如果有多个A等距，由构造者指定选取那个A），扩张最小包含圆到c1，使c1包含A和原先在c0边界上的所有点，此过程定义为一次扩张。
扩张直到所有的点都包含在ck内时结束。构造的目标是使扩张次数k尽可能的多。探讨对于某个n的k的最大值。
对于比较小的n值：
n=3则k=0；
n=4则k=2；

aimisiyou

@zhouguang  目前已知的最小包围圆算法都是你所说的这样，是通过不断扩大圆来得到结果。但我想通过先找一个包含所有点的圆，然后不断缩小该圆来得到结果，达到异曲同工的效果。这就需要先找到一个“合理”的点（要求距该点最远的点必在点集最小包围圆上），后面的算法处理就很简单了。

aimisiyou

@gxqcn $$令P_i=(x_i,y_i) ,则P_0=(\frac{x_{min}+x_{max}}{2},\frac{y_{min}+y_{max}}{2}),d_i=|P_0P_i|,\lambda_i=\frac{d_i}{\sum{d_i}},
P=(\sum{\lambda_ix_i},\sum{\lambda_iy_i}),
则到P最远的点是否必在点集最小包围圆上？
$$

kastin

aimisiyou 发表于 2016-11-5 15:41
@gxqcn $$令P_i=(x_i,y_i) ,则P_0=(\frac{x_{min}+x_{max}}{2},\frac{y_{min}+y_{max}}{2}),d_i=|P_0P_i|,\ ...

之前有段时间对计算几何比较感兴趣，关于这个问题也查阅了不少资料，下面这两篇关于最小包围圆（球）的论文可以说是比较经典的，方法对于任意维都适用
Bernd GÄartner Fast and Robust Smallest Enclosing Balls
Emo Welzl Smallest enclosing disks (balls and ellipsoids)
上述论文中也有相关的性质的讨论，你的很多问题都能从中找到答案或是启示。

另外，问题还可以推广到圆集的最小包围圆（球集的最小包围球），有一篇国外的博士论文对此有非常精彩的论述（当然有上述两作者的指导）
Smallest enclosing balls of balls Combinatorial structure & algorithms

上述文章网上都可下载。

aimisiyou

看来要恶补英语了……