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

aimisiyou

哦，仔细看了编辑后的5#楼，明白了。原来我检测算法的数据没遇到这种情况，看来是我的运气太好了。多谢了！

aimisiyou

想了下，若按我的算法，得到的“最小包围圆”为过A、B、C三点的圆，看来最后还要加个判断才行（即角p2p1p3为锐角才行，此例中角BCA为钝角）。

aimisiyou

gxqcn+发表于+2014-12-29+21:51+我构造了一个反例，如下图：+

这个反例构造的真的很巧妙，对你的佩服犹如……，同时从某方面应征了就算计算机验证99。99……％正确也不代表证明了问题的结论。

aimisiyou

再进一步，若改成距点集重心\(\left(\overline{x}=\dfrac{\sum x_i}{n},\; \overline{y}=\dfrac{\sum y_i}{n}\right) \)最远的点必在点集的最小包围圆上是否正确？

aimisiyou

显然，对于三个点都是成立的！

aimisiyou

对于四个点，我们可以取一等腰梯形来验证。

aimisiyou

以等腰梯形的重心为坐标原点建立坐标系 ，四点坐标分别为\(A(-a，h)、B(a，h)、C(-b，-h)、D(b，-h)\)，此时最小包围圆圆心坐标为\(Q\left(0,\dfrac{a^2-b^2}{4h}\right)\)若\(C\)点向圆内偏移微小距离\((x，y)\)至\(C’（-b+x，-h+y）\)，则重心\(O\)偏移\(\left(\dfrac{x}{4}，\dfrac{y}{4}\right)\)至\(O'\left(\dfrac{x}{4}，\dfrac{y}{4}\right)\),此时有\(QC'<r\),若同时满足\(O'C'>O'D\),则证明存在反例。

gxqcn

再进一步，若改成距点集重心\(\left(\overline{x}=\dfrac{\sum x_i}{n},\; \overline{y}=\dfrac{\sum y_i}{n}\right) \)最远的点必在点集的最小包围圆上是否正确？

仍然不成立！

构造反例思路如下：

• 平面有一正六边形，几个顶点均匀分布，则其重心必为其中心，最小包围圆必为其外接圆；
• 将上述 n 个图形叠放，相当于每个顶点处实际上有 n 个点（n 足够大）；
• 在某一顶点处，仅保留某一个单点（其余 (n-1) 个点剔除），显然其最小包围圆保持不变，但重心位置远离该点；
• 将该点从最小包围圆上稍微向圆心移动，使之不在该圆上；
  

最后那步，由于单点的权重较低，在其调整过程中，整个点集重心的位置变化远小于该点的位置变化，
如此一来，该点仍可保持为点集中最远离重心的那个点，而它却并不在这些点集的最小包围圆上！

上述构造按说也是比较巧妙的，
并非得正六边形，其实正三角形、正方形等也可以，只是我第一感觉就用的是正六边形。

aimisiyou

gxqcn 发表于 2015-10-30 13:37
仍然不成立！

构造反例思路如下：

感觉是那么回事，如果有不等式佐证下更好！

gxqcn

不用不等式去佐证。

你想象一下加权质点的问题：

均匀分布的同质量的一系列质点，用一个“零质量”的质点替代某一个质点，
在上述过程中，最小包围圆保持不变（仅于位置相关）；质心（还与权重相关）将漂移，并远离该“零质量”的质点，
而“零质量”的质点无论如何游荡，新的质心却保持不动，
所以嘛，很容易构造出你需要的反例。