11.多边形的三角剖分 (Triangulation) ： 画廊问题

目录

1.Methodology

​编辑2. Definition

3. Lower & Upper Bound

4.Hardness

5.Approximation & Classification

6. Necessity of floor(n/3)

---

1.Methodology

多边形三角剖分

点集三角剖分 

2. Definition

假设存在一个艺术馆，里面存在很大艺术品需要看管，那最少需要多少个哨兵才能覆盖呢？

任意给定一个多边形P， 如果要足以用一些点(哨兵)将其覆盖的话，这个哨兵的几何最少能够达到多少？

红色为哨兵，黄色为覆盖的部分

是否可以用更少的哨兵呢？

不能，因为绿色的点只用一个哨兵覆盖不到。

3. Lower & Upper Bound

上述多边形，凸包，星形多边形只需要一个哨兵就可以了

最差的情况是什么样的呢？
如果是n个点组成的多边形，最多需要n个摄像头

4.Hardness

怎么给出画廊的最优的方案？

这是一个NP hard 的问题

5.Approximation & Classification

6. Necessity of floor(n/3)

证明：

任何一个多边形都可以分解为多把扇子，而且不会超过 n/3 把