查看“︁美术馆问题”︁的源代码

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

== 二维情形 ==
[[Image:Art gallery problem.svg|thumb|四個守衛可以監視整個美術館。]]
美术馆问题最初由美国数学家 Victor L. Klee 在 1973 年提出. 。

许多原始问题的变种也被称为美术馆问题。在一些版本中守卫被限制在边界上，甚至被限制在多边形的[[頂點 (幾何)|顶点]]处。有些版本仅需守卫能够监视美术馆的所有墙壁或墙壁的一部分。

对于守卫只能处于[[頂點 (幾何)|顶点]]并且只需监视顶点的情况等价于多边形的[[可见性图]]的[[控制集问题]]。

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

=== Chvátal 美术馆定理 ===
Chvátal {{vanchor|美术馆定理}}<ref name=Chvatal>{{citation|first=V.|last=Chvátal|authorlink=Václav Chvátal|title=A combinatorial theorem in plane geometry|journal=Journal of Combinatorial Theory, Series B|volume=18|pages=39–41|year=1975|doi=10.1016/0095-8956(75)90061-1}}.</ref> 给出了一个守卫最少数量的一个[[上界]]。这个定理陈述说 <math>\left\lfloor n/3 \right\rfloor</math> 个守卫足够充分(在某些时候必要)用来监视一个 <math>n</math> 个[[頂點 (幾何)|顶点]]的简单多边形。

=== Fisk 的简短证明 ===
[[File:Triangulation 3-coloring.svg|thumb|對一個三角化的多邊形做關於頂點的三-塗色。]]
首先，将用多边形内互不相交的对角线将多边形三角化。然后用三种不同的颜色对多边形的[[頂點 (幾何)|顶点]]上色，使得多边形内的每个三角形的都含有涂有不同颜色的顶。 这可以通过选定一个三角形对它的顶点涂以不同的颜色, 将其扩展到与其相邻的三角形具有唯一的方案。由于三角化的[[对偶图]]是一个[[树]]，我们可以继续下去直至所有的顶点被涂色。在其中的任何一种颜色的全部顶点上放置守卫就可以监视整个多边形：假设使用红、黄、蓝三种颜色，守卫被放置在所有红色的顶点上，由于每个三角形都有一个红色的顶点，并且在这个顶点上可以监视整个三角形,，样所有的三角形都在守卫的监视之中。

===计算复杂性===

== 三维情况 ==
[[Image:Polyhedron with no vertex visible from center.png|thumb|這個範例多面體的內部有一些點，是從任何頂點都看不到的。]]
如果美術館是用一個三維[[多面體]]來描述，那麼在每個頂點上放上守衛，並不能保證整個美術館都在守衛的監視範圍。雖然多面體的整個表面都會被監視，但有一些多面體的內部點有可能不會被監視到。<ref>{{harvtxt|O'Rourke|1987}}, p.&nbsp;255.</ref>

<references/>
[[Category:計算幾何]]
[[Category:数学问题]]