【名题赏析】3.1 三角形剖分、画廊问题和卡特兰数（1）

解名题，学数学！我个人最喜欢的一个主题！...

上图展示了这样的图形处理技术：把一个复杂图形（例如 IRON MAN）分割成互不重叠的简单图形（例如三角形、四边形等），这种技术称为 “剖分”。

通过剖分，我们可以告诉计算机一个复杂图形的每个微小局部的细节，例如：位置、大小、染色、亮度、对比度等等，再将所有局部组合起来，从而构建出整个图像的基本面貌。剖分越仔细，越接近真实的图像。下面是更多例子：

为了避免因细枝末节的讨论而偏离主线，本节将主题限定在多边形的三角形剖分（Polygon Triangulation 下称三角形剖分），也即：不添加新顶点，将一个多边形完整地分割成互不重叠的三角形的方法。

注：这里的多边形是指简单多边形，即它是一个封闭的折线段，各边除了端点外没有其它交点。如下图说明的那样：

换个角度来看，所谓三角形剖分即要找到如何利用 “多边形内部 ”的对角线（因为有凹多边形的情形）将多边形 “ 降解 ” 为若干个三角形的方法。下图为一个九边形的两个不同的剖分：

多边形的三角形剖分主要解决以下几个问题：

（1）三角形剖分总是可能的么？有没有不可以剖分的多边形。

（2）如果可以三角形剖分，例如凸 n 边形，则不同的剖分方法有几种？（Catalan Num. 卡特兰数）

（3）任意指定一个多边形，如何设计程序让计算机可以快速地进行三角形剖分。如何定义并确定最优化的剖分？在回答上面几个疑问之前，我们先转向一道非常著名的题目：画廊问题（Art Gallery Problem），该问题于 1973 年由 Victor Klee 提出，并很快就被 Vaclav Chavtal 解决，不过他的证明方法着实复杂。1978 年，Steve Fisk 给出了一个极其优美的论证，这个论证会利用到三角形剖分。在正式解答之前，大家不妨思考一下画廊问题：

画廊问题（Art Gallery Problem）：

一个展览馆画廊的墙形成一个 n 边多边形（可凸可凹）。保安位于画廊内某些固定位置。假设保安能转头，但不能走动，为了保证每寸墙都能被保安看到，最少需要多少保安？

答案当然不是 1，请考虑最坏的情况！下面是一些提示性的例子，其中 n 表示边数，G 表示最少的保安数量。你能找到 G 关于 n 的函数关系式么？试试看！

    关注 初中理科班数学