三七二十一
LUCKY !

美术馆定理

n 边形美术馆中 ⌊n/3⌋ 个警卫总是足够的,这是最优界。Václav Chvátal 1975年用三角剖分和三色染色证明。

⌊n/3⌋ guards always sufficient for an n-gon.

变体问题

直角美术馆:⌊n/4⌋;正交多边形:⌊n/4⌋;三维美术馆:NP-困难!移动警卫问题仍在研究中。

返回