美術館問題

美術館問題或博物館問題是計算幾何中的一種可見性問題，來源於現實世界中的看守美術館的問題：如何用最少的守衛看守美術館，並使得美術館的每個角落都在守衛的視野之中。在計算幾何的版本中，美術館的形狀被表示為一個簡單多邊形並且每個守衛被表示為該多邊形內的一個點。稱一個點集 $S$ 能夠守衛一個多邊形，如果對多邊形內的每個點 $p$ ,存在點 $q\in S$ 使得連接 $p$ 和 $q$ 的線段在多邊形的內部。

二維情形

四個守衛可以監視整個美術館。

美術館問題最初由美國數學家 Victor L. Klee 在 1973 年提出. 。

許多原始問題的變種也被稱為美術館問題。在一些版本中守衛被限制在邊界上，甚至被限制在多邊形的頂點處。有些版本僅需守衛能夠監視美術館的所有牆壁或牆壁的一部分。

對於守衛只能處於頂點並且只需監視頂點的情況等價於多邊形的可見性圖的控制集問題。

問題描述

假設有一個 $n$ 邊形的美術館, 需要多少個固定的守衛來監視整個美術館？每個守衛被看做是一個固定的點，並且具有全方位的視野，即具有$2\pi$ 的視線範圍。當然一個守衛的視線不能透過美術館的牆壁。一個等價的問題是：需要多少盞燈來完全照亮整個房間。

Chvátal 美術館定理

Chvátal 美術館定理 給出了一個守衛最少數量的一個上界。這個定理陳述說 $\left\lfloor n/3\right\rfloor$ 個守衛足夠充分(在某些時候必要)用來監視一個 $n$ 個頂點的簡單多邊形。

Fisk 的簡短證明

對一個三角化的多邊形做關於頂點的三-塗色。

首先，將用多邊形內互不相交的對角線將多邊形三角化。然後用三種不同的顏色對多邊形的頂點上色，使得多邊形內的每個三角形的都含有塗有不同顏色的頂。 這可以通過選定一個三角形對它的頂點塗以不同的顏色, 將其擴展到與其相鄰的三角形具有唯一的方案。由於三角化的對偶圖是一個樹，我們可以繼續下去直至所有的頂點被塗色。在其中的任何一種顏色的全部頂點上放置守衛就可以監視整個多邊形：假設使用紅、黃、藍三種顏色，守衛被放置在所有紅色的頂點上，由於每個三角形都有一個紅色的頂點，並且在這個頂點上可以監視整個三角形,，樣所有的三角形都在守衛的監視之中。

三維情況

這個範例多面體的內部有一些點，是從任何頂點都看不到的。

如果美術館是用一個三維多面體來描述，那麼在每個頂點上放上守衛，並不能保證整個美術館都在守衛的監視範圍。雖然多面體的整個表面都會被監視，但有一些多面體的內部點有可能不會被監視到。