至少需要多少名守卫？
阅读(82)
计算几何
可见性问题
收录于
老少皆宜 -- 2021年02月08日
老少皆宜 -- 2021年02月08日摘要
如何用最少的守卫看守美术馆, 使得美术馆的每个角落都在守卫的视野之中.
美术馆问题最初由美国数学家 Victor L. Klee 在 1973 年提出.
美术馆问题是计算几何中的一种可见性问题，来源于现实世界中的看守美术馆的问题: 如何用最少的守卫看守美术馆, 并使得美术馆的每个角落都在守卫的视野之中.
在计算几何的版本中, 美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点. 称一个点集
能够守卫一个多边形, 如果对多边形内的每个点
,存在点
使得连接 和
的线段在多边形的内部.
展开正文...
前往题库
等 25 人参与了问题讨论
题目
美术馆的形状表示为图中紫色不规则的多边形（由若干个全等的正方形组成）.请你安排守卫的位置（守卫不能移动，也没有透视眼）使得美术馆的每个角落都在守卫的视野之中.那么至少需要多少名守卫看守美术馆？__________.
选项
3
4
5
6
提交
等 25 人参与了问题讨论
步骤1
4名守卫的一种可行站位如图所示，这样整个美术馆都能被监控到.
步骤2
接下来证明4名守卫是必须的，我们将通过选取美术馆内4个特殊的位置来说明.
图中4个星型分别标记为4种不同的颜色，而这4个位置是必须被监控到的，涂色的4块区域分别是守卫能站的位置以监控到对应的星型位置，但是四块区域没有公共部分，这说明任何一名守卫都只能看到一个星型位置，因此3名守卫是不可行的.