美术馆问题

美术馆问题或博物馆问题是计算几何中的一种可见性问题, 来源于现实世界中的看守美术馆的问题: 如何用最少的守卫看守美术馆, 并使得美术馆的每个角落都在守卫的视野之中. 在计算几何的版本中, 美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点. 称一个点集 $S$ 能够守卫一个多边形, 如果对多边形内的每个点 $p$ ,存在点 $q\in S$ 使得连接 $p$ 和 $q$ 的线段在多边形的内部.

二维情形

四个守卫可以监视整个美术馆。

美术馆问题最初由美国数学家 Victor L. Klee 在 1973 年提出.

许多原始问题的变种也被称为美术馆问题. 在一些版本中守卫被限制在边界上, 甚至被限制在多边形的顶点处. 有些版本仅需守卫能够监视美术馆的所有墙壁或墙壁的一部分.

对于守卫只能处于顶点并且只需监视顶点的情况等价于多边形的可见性图的控制集问题.

问题描述

假设有一个 $n$ 边形的美术馆, 需要多少个固定的守卫来监视整个美术馆？每个守卫被看做是一个固定的点, 并且具有全方位的视野, 即具有 $2\pi$ 的视线范围. 当然一个守卫的视线不能透过美术馆的墙壁. 一个等价的问题是: 需要多少盏灯来完全照亮整个房间.

Chvátal 美术馆定理

Chvátal 美术馆定理^[1] 给出了一个守卫最少数量的一个上界. 这个定理陈述说 $\left\lfloor n/3\right\rfloor$ 个守卫足够充分(在某些时候必要)用来监视一个 $n$ 个顶点的简单多边形.

Fisk 的简短证明

对一个三角化的多边形做关于顶点的三-涂色。

首先, 将用多边形内互不相交的对角线将多边形三角化. 然后用三种不同的颜色对多边形的顶点上色, 使得多边形内的每个三角形的都含有涂有不同颜色的顶点. 这可以通过选定一个三角形对它的顶点涂以不同的颜色, 将其扩展到与其相邻的三角形具有唯一的方案. 由于三角化的对偶图是一个树, 我们可以继续下去直至所有的顶点被涂色. 在其中的任何一种颜色的全部顶点上放置守卫就可以监视整个多边形: 假设使用红、黄、蓝三种颜色, 守卫被放置在所有红色的顶点上, 由于每个三角形都有一个红色的顶点, 并且在这个顶点上可以监视整个三角形, 这样所有的三角形都在守卫的监视之中.

计算复杂性

三维情况

这个范例多面体的内部有一些点，是从任何顶点都看不到的。

如果美术馆是用一个三维多面体来描述，那么在每个顶点上放上守卫，并不能保证整个美术馆都在守卫的监视范围。虽然多面体的整个表面都会被监视，但有一些多面体的内部点有可能不会被监视到。^[2]

^ Chvátal, V., A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B, 1975, 18: 39–41, doi:10.1016/0095-8956(75)90061-1 .
^ O'Rourke (1987), p. 255.

[Chvatal-1] Chvátal, V., A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B, 1975, 18: 39–41, doi:10.1016/0095-8956(75)90061-1 .

[2] O'Rourke (1987), p. 255.

[1]

[2]