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

aimisiyou

我写的求平面n个点的最小包围圆代码基于这一假设，即做一个该点集的任意方向的外接矩形，则点集的最小包围圆必过距该外接矩形对角线交点最远的点。
谁能给出严谨证明来证明该假设是对的还是错的？

mathe

显然错误的结论，圆心不一点在矩形中心。三个点都不成立

aimisiyou

我知道圆心不一定是矩形中心，但我只是说最小包围圆必过到外接矩形中心最远的点。
三个点的情况显然是成立的，不会有例外。
1）如果3点构成锐角三角形，最小包围圆即三角形的外接圆，它过所有的点，所以成立。
2）如果3点构成钝角三角形，至少有一个点位于外接矩形的顶点（抽屉原理），并且必是一个锐角顶点（因含于矩形内角），而钝角顶点不可能位于外接矩形的顶点上，不可能是最远点。我们知道最小包围圆就是以钝角对边为直径的圆，并且钝角顶点在圆内。所以对于钝角三角形的情况也成立。
3）三点共线是钝角三角形的极限情况，同2）也成立。

aimisiyou

贴出我的算法：
1、先求第一点p1，p1为到点集包围矩形对角线交点最远的点，此时包围圆过p1且以对角线交点为圆心；
2、缩小包围圆，圆心向p1移动，圆半径缩小，直至第二点p2在圆上;
3、以P1、P2为弦，剩余点中对p1、p2构成的张角最小的点为p3（若最小张角为钝角，则p1p2为直径）；
4、检验角p1p2p3是否为锐角，若是则最小包围圆过p1p2p3；否则以p1p3为弦，返回步骤3（再循环一次必然成立）。

gxqcn

我构造了一个反例，如下图：

会是反例吗？

• 作一正八边形，其8个顶点（金色）属于考察点集的一部分，则其“最小包围矩形”一定为一个正方形；
• 接下来在该正方形内（含四边），正八边形外适当添加点，如点A、点B（绿色）(让两点对称于对角线)；
• 过上述已知点做最小包围圆（绿色圆），白色点为圆心，在对角线向左上偏离了正方形中心O一段距离；
• 然后以正方形的中心O为圆心，以OA长为半径画圆（红色圆）。

红绿两圆相交于A、B两点，易见两圆优弧AB红外绿内，那么两圆劣弧AB红内绿外。（由于两段劣弧几近重合，不得不如此反推）。
可见在两圆劣弧间的点（不含边界）既位于正方形内和最小包围圆内，距正方形中心O的距离又比OA更长，所以构成反例。

gxqcn

你这个“猜想”描述起来都很拗口，举反例也相当不易。

我先说一下构造思路，数值验证部分就由楼主（或熟悉数学软件的网友）来完成吧：

• 为什么选正方形？因为它是最特殊的“矩形”，如果研究的点集全部限定在一个正方形内（含四边），问题会简单很多；
• 为什么会想到正八边形？因为两点决定一条直线，它的最小外围矩形，必为正方形，且各顶点离正方形中心距离相等，问题也会简化很多；
• 此时的最小外围圆，必为正八边形的外接圆；
• 让圆动起来！在正方形左上角的两边对称的取两点A、B，为了包围该两点，外围圆半径不得不扩大，圆心向左上方偏移；
• 以正方形中心O为圆心，以OA为半径再作一段圆弧，肯定交正方形左上角分别于点A、点B（由上一步骤可保证）；
• 如果上一步骤得到的圆弧在最小外围圆的内部，即新圆弧在两段弧夹成的“月牙”形内侧的话，则随便在“月牙”内部（不含边界）选择一点C作为新加的考察点，那么点C就同时满足两个要求：它是距最小外围矩形对角线交点最远的点，但最小外围圆却不经过它！
  

对于打红字描述的部分，善于计算机几何作图的朋友可以重新画一个标准的图来直观明示，
或者选取特殊位置的点A、B，通过数值计算的方法来验证或推翻上述结论，
这两项皆非本人强项，我就不继续参与了。

hujunhua

郭老板确实构造了一个巧妙的反例，但是这个反例要直观地画出来却不太好看，因为那个月牙形太窄了，内外两段圆弧几乎重叠了，要画很大的图才看得清差距来。

aimisiyou

gxqcn+发表于+2014-12-30+08:09+你这个“猜想”描述起来都很拗口，举反例也相当不易。+我先说一下构造思路，数值验证部分就由楼主（或熟+...

你好像忽略了个问题，首先你确定在正方形坐上角两对称点A,B，当然此时正八边形的八个顶点及A,B两点共10点的最小包围圆必与圆OA相交，但相交的弦不一定就是A,B啊，好你此时又往点集中加入这两点，相交的弦又在别处……你构造不出来了

aimisiyou

aimisiyou+发表于+2014-12-30+12:24+你好像忽略了个问题，首先你确定在正方形坐上角两对称点A,B，当然此时正八边形的八个顶点及A,B两点共10点+...

经作图，你所说的情况最小包围圆只过A,B中的一点，另两点为正八边形两顶点。

hujunhua

5#的图我已更新为用几何画板所作的较准确的图，文字部分也有编辑，直观地说明了反例成立的理由。愿楼主能看明白。

A、B是对称于对角线的，最小包围圆过其中一点，则必过另一点，哪有只过一点之理？