平面点集F的最小覆盖圆周上，必定至少存在两个F中的点

abababa

如题，设$F$是平面上的有限点集，$\odot O$是能覆盖$F$的最小的圆，则$\odot O$的边界上至少有两个$F$中的点。

这个看着挺直观的，假设只有一个，那么能用一个更小的圆覆盖，但怎么证明呢？

Aluminiumor

题目似乎应该多加一些限制条件，否则，取
$$\mathbf{F}=\{(x,y)|x^2+y^2<1\}$$
不满足题意。

abababa

Aluminiumor 发表于 2024-7-30 19:38
题目似乎应该多加一些限制条件，否则，取
$$\mathbf{F}=\{(x,y)|x^2+y^2<1\}$$
不满足题意。 ...

是的，我忘了加有限的条件，我在主楼补充上。谢谢提醒。

Aluminiumor

若 $\odot O$ 的边界上只有一个 $\mathbf{F}$ 中的点。
不妨设 $\odot O:x^2+y^2=1$, 该点为$(0,1)$ （总能通过变换得来）
考虑与 $\odot O$ 相切的直线 $2m\cdot x+2n\cdot y=\pm2\sqrt{m^2+n^2}$
对于 $\mathbf{F}$ 中的其他点 $(x_i,y_i)$, 都有$|2m\cdot x_i+2n\cdot y_i|<2\sqrt{m^2+n^2}$
设 $\mathbf{F'}=\mathbf{F}-\{(0,1)\}$ , $d=\max\{x^2_i+y^2_i|(x_i,y_i)\in\mathbf{F'}\}$ 则 $d\in[0,1)$
则 $$(x_i-m)^2+(y_i-n)^2=x_i^2+y_i^2-(2m\cdot x_i+2n\cdot y_i)+m^2+n^2<d+m^2+n^2+2\sqrt{m^2+n^2}$$
取 $m=\sin\theta\cos\theta,n=\sin^2\theta,\theta\in\left(0,\pi\right)$, 则 $m^2+(n-1)^2=\cos^2\theta<1$
且 $$d+m^2+n^2+2\sqrt{m^2+n^2}=d+\sin^2\theta+2\sin\theta$$
总能选取合适的 $\theta$, 使 $d+\sin^2\theta+2\sin\theta\leq\cos^2\theta\Longleftrightarrow \sin^2\theta+\sin\theta\leq\dfrac{1-d}{2}$
此时存在 $\odot O':(x-\sin\theta\cos\theta)^2+(y-\sin^2\theta)^2=\cos^2\theta$ 可以覆盖 $\mathbf{F}$, 与假设矛盾。
若 $\odot O$ 的边界上没有一个 $\mathbf{F}$ 中的点，同理可证矛盾。
故 $\odot O$ 的边界上至少有两个 $\mathbf{F}$ 中的点.

abababa

Aluminiumor 发表于 2024-7-31 06:38
若 $\odot O$ 的边界上只有一个 $\mathbf{F}$ 中的点。
不妨设 $\odot O:x^2+y^2=1$, 该点为$(0,1)$ （总能 ...

谢谢。有几个地方没看懂，切线里的$m,n$是什么？是在后面要确定的值吗？那这样的话，点到直线的距离应该小于$2$吧。比如$\odot O$上一点$(\cos\alpha,\sin\alpha)$处的切线为$x\cos\alpha+y\sin\alpha-1=0$，这样$F'=F\setminus\{(0,1)\}$中任意一点$(x_i,y_i)$到切线的距离为
\[\frac{\abs{x_i\cos\alpha+y_i\sin\alpha-1}}{\cos^2\alpha+\sin^2\alpha}=\abs{x_i\cos\alpha+y_i\sin\alpha-1}<2\]
能得到$0\le\abs{x_i\cos\alpha+y_i\sin\alpha}<3$，但这个值在后面不好用。

abababa

abababa 发表于 2024-7-31 15:53
谢谢。有几个地方没看懂，切线里的$m,n$是什么？是在后面要确定的值吗？那这样的话，点到直线的距离应该 ...

我没能证明出结果来，下面是我的一点想法：
首先按4楼的提示，不妨设$\odot O:x^2+y^2=1$是$F$的最小覆盖圆，且边界上只有$F$中的唯一一点$(1,0)$。然后假设已经能找到新的最小覆盖圆$\odot O'$，直观地看$\odot O'$的圆心应该靠近$(1,0)$一侧，设圆心$O'=(r\cos\theta,r\sin\theta)$。设$F'=F\setminus\{(1,0)\}$，对任意的$(x_i,y_i)\in F'$都有$x_i^2+y_i^2<1$，设$d=\max\{x_i^2+y_i^2\}$，则$d<1$。需要$\odot O'$能成为覆盖圆，则必有
\[
\begin{cases}
(x_i-r\cos\theta)^2+(y_i-r\sin\theta)^2<1&\text{$F'$中的点都在$\odot O'$中}\\
(1-r\cos\theta)^2+(1-r\sin\theta)^2<1&\text{$(1,0)$在$\odot O'$中}
\end{cases}
\]
在方程组的不等号中间插入一个可能的值，就是
\[
\begin{cases}
(x_i-r\cos\theta)^2+(y_i-r\sin\theta)^2\le d-2r(x_i\cos\theta+y_i\sin\theta)+r^2<1\\
(1-r\cos\theta)^2+(1-r\sin\theta)^2=1-2r\cos\theta+r^2<1
\end{cases}
\]

也就是只要能找到满足上式的$r$和$\theta$，就能确定圆心$O'$，并且是更小的覆盖圆。

后面我就没能做出来了。

Aluminiumor

abababa 发表于 2024-7-31 15:53
谢谢。有几个地方没看懂，切线里的$m,n$是什么？是在后面要确定的值吗？那这样的话，点到直线的距离应该 ...

我一开始待定更小的圆为$(x-m)^2+(y-n)^2=r^2$,  之后再确定合适的 $m,n,r$ 的值。
我选择了 $m=\sin\theta\cos\theta,n=\sin^2\theta,r=\cos\theta$.
"点到直线的距离应该小于$2$吧" 与我的过程没有矛盾吧。

abababa

Aluminiumor 发表于 2024-7-31 18:24
我一开始待定更小的圆为$(x-m)^2+(y-n)^2=r^2$,  之后再确定合适的 $m,n,r$ 的值。
我选择了 $m=\sin\the ...

我明白这个$\abs{2mx_i+2ny_i}<2\sqrt{m^2+n^2}$的意思了，这是指直线一侧的半平面。

后面我还有些疑问，就是$d+m^2+m^2+2\sqrt{m^2+n^2}=d+\sin^2\theta+2\sin\theta$这里，目标是让它小于$1$吧，这里这个$d$的范围是$0<d<2$。我设$m^2+n^2=r^2,(r>0)$，就需要使$d+r^2+2r<1$，也就是$(r+1)^2<2-d$，但这个不一定有解，比如$d\to2$时就没有解了。

换成4楼的式子，就是需要$\sin^2\theta+\sin\theta\le\frac{1-d}{2}$，配方得$(\sin\theta+\frac{1}{2})^2\le\frac{1-2d}{4}$，当$d\to2$时右边是负数，就没有实数解了。

Aluminiumor

abababa 发表于 2024-7-31 19:40
我明白这个$\abs{2mx_i+2ny_i}<2\sqrt{m^2+n^2}$的意思了，这是指直线一侧的半平面。

后面我还有些疑问 ...

$d\in[0,1)$

abababa

Aluminiumor 发表于 2024-7-31 21:25
$d\in[0,1)$

是的，我又弄错了，总把$d$当直径。可当$d\to1$时，$\sin^2\theta+\sin\theta\le\frac{1-d}{2}\iff(\sin\theta+\frac{1}{2})^2\le\frac{1-2d}{4}$还是没有实数解。

我明白了，是我弄错符号了。

Aluminiumor

abababa 发表于 2024-8-1 11:24
是的，我又弄错了，总把$d$当直径。可当$d\to1$时，$\sin^2\theta+\sin\theta\le\frac{1-d}{2}\iff(\sin\ ...

$(\sin\theta+\frac12)^2\leq\frac{3-2d}{4}$