华容道 发表于 2012-11-9 19:27:04

覆盖问题

平面上有100个点且任意两个点之间的距离均不超过1,若一个圆必可以将这些点覆盖,求这个圆半径的最小值。

祭司zhangcy 发表于 2012-11-9 20:00:26

三分之根号三

华容道 发表于 2012-11-9 20:31:33

祭司zhangcy 发表于 2012-11-9 20:00 static/image/common/back.gif
三分之根号三

能给出个证明么?:handshake

祭司zhangcy 发表于 2012-11-9 20:47:13

华容道 发表于 2012-11-9 20:31 static/image/common/back.gif
能给出个证明么?

我考虑了一种比较极端的情况,就是一个边长为1的正三角形。然后以每个角顶点为中心做圆,然后其他所有点都应该在三个圆都相交的地方,。推广开来,用一个半径为三分之根号三的圆就能覆盖这个区域。

好吧,其实我只是随便想想,答案应该是正确的,但是过程太水了。还给不出严密的证明

华容道 发表于 2012-11-9 21:58:13

祭司zhangcy 发表于 2012-11-9 20:47 static/image/common/back.gif
我考虑了一种比较极端的情况,就是一个边长为1的正三角形。然后以每个角顶点为中心做圆,然后其他所有点都 ...

谢谢您的回复:handshake这个问题的证明很让我纠结。

小鸿99 发表于 2012-11-9 22:26:10

我觉得不太对,应该是二分之一
在一个半径为1/2的圆中,任意两点的最大距离为直径的长度,即为1,所以一个半径为1/2的圆应该够了
(1/2)>(√3/3)

superacid 发表于 2012-11-9 23:40:21

本帖最后由 superacid 于 2012-11-9 23:42 编辑

小鸿99 发表于 2012-11-9 22:26 static/image/common/back.gif
我觉得不太对,应该是二分之一
在一个半径为1/2的圆中,任意两点的最大距离为直径的长度,即为1,所以一个 ...

但是,1/2<sqrt(1/3)

桃园隐士 发表于 2012-11-10 08:04:29

原来是这样....

祭司zhangcy 发表于 2012-11-10 09:37:14

小鸿99 发表于 2012-11-9 22:26 static/image/common/back.gif
我觉得不太对,应该是二分之一
在一个半径为1/2的圆中,任意两点的最大距离为直径的长度,即为1,所以一个 ...

可是半径1/2的圆却不能覆盖一个边长为1的正三角形。。。。

天方魔 发表于 2012-11-10 10:19:33

小鸿99 发表于 2012-11-9 22:26 static/image/common/back.gif
我觉得不太对,应该是二分之一
在一个半径为1/2的圆中,任意两点的最大距离为直径的长度,即为1,所以一个 ...

干吗要最大长度,直接所有点直接覆盖不就行了,所以圆也可以看做一个点。
页: [1] 2
查看完整版本: 覆盖问题