A. Art Gallery Problem
数学大学
A. Art Gallery Problem
计算几何 · 03. Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
A. Art Gallery Problem
计算几何 · 03. Triangulation
Definition
艺术画廊问题：最少需要多少名守卫（ placement 在顶点上）才能看住整个画廊？
模型
简单多边形，守卫在顶点处 360° 视野
目标
最坏情况下的最少守卫数
Lower & Upper Bounds
上界 ⌊n/3⌋：任何 n 个顶点的简单多边形都能被这么多守卫看住；下界：存在需要 ⌊n/3⌋ 个的多边形。
上界
⌊n/3⌋ 由三染色构造给出
下界构造
n/3 个「尖刺梳子」每刺需一名守卫
Hardness
求最少守卫的精确数是 NP 难：带洞多边形与最小化版本都难。
NP 难
顶点守卫最小化是 NP 难问题
变体
带洞多边形、正交多边形的界与难度不同
Approximation & Classifi
近似与分类：实用中用近似算法或按多边形类型分类处理。
近似
对数近似比的贪心集合覆盖
分类
按「无洞正交」等子类分别套用更紧的界
本节要点
- ✓⌊n/3⌋ 守卫上界与匹配的下界
- ✓最小化是 NP 难
- ✓实用走近似或子类分类
延伸主题：画一个需要 ⌊n/3⌋ 守卫的梳子了解贪心近似算法
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1上界与下界都等于 ⌊n/3⌋，这说明什么？
参考答案说明 ⌊n/3⌋ 是精确的最坏情况答案：既存在总能奏效的守卫方案（上界可达），又存在无法更省的实例（下界贴住）。问题的「最坏情形复杂度」被完全确定。
2守卫为什么限定在顶点而不是任意位置？
参考答案顶点守卫是经典版本的限制：便于用图论（顶点支配）刻画。任意位置守卫（点守卫）的最优化与近似性都更复杂——可以放在边上的守卫有时更省，但算法难度陡增。
3带洞多边形的守卫界为什么不再是 ⌊n/3⌋？
参考答案洞破坏了「外平面图可三染色」的前提：剖分图不再外平面，三染色可能不存在。带洞多边形需要 Θ(n) 级的守卫（最坏情形），问题难度也升为 NP 难。