单调多边形三角剖分：计算几何的高效算法

"单调多边形的三角剖分是计算几何中的一个重要概念，主要应用于计算流体力学和传热学等领域。陶文全的讲解聚焦于如何高效地进行这一过程。在计算几何中，多边形的三角剖分是将一个多边形划分为一系列互不相交的三角形，这对于数值模拟、图形渲染等多种任务至关重要。 首先，提到的"单调多边形"是指在垂直方向上，其边界顶点按照y坐标严格递增或递减的多边形，即没有水平边。严格y-单调多边形的三角剖分相对简单，因为可以沿边界链从高顶点向低顶点推进，引入对角线。在处理过程中，算法按照y坐标递减的顺序处理顶点，并使用一个栈S作为辅助数据结构，栈中存放未完全处理的顶点。 算法的运行时间分析是关键。初始构建优先队列Q和初始化树T需要线性时间，事件点的处理时间复杂度为O(logn)，因为优先队列和平衡查找树的操作通常在O(logn)时间内完成。每处理一次事件点，可能会涉及到一次查找、插入和删除操作，以及对D（对角线集合）的O(1)时间的插入。因此，总时间复杂度为O(nlogn)，空间复杂度为O(n)，因为每个顶点和边最多存储一次。 通过引理3.5和定理3.6，我们可以得知如何在O(nlogn)时间内将包含n个顶点的简单多边形分解为y-单调子块，进而实现对单调多边形的线性时间三角剖分。这是对之前需要平方量级时间算法的显著改进。 《计算几何——算法与应用》这本书由Mark de Berg等人撰写，邓俊辉翻译，详细介绍了计算几何的多个核心主题，包括线段求交、多边形三角剖分、线性规划、正交区域查找、点定位、Voronoi图以及排列与对偶等。书中的每个章节都包含了专题讨论、注释、评论和习题，为深入理解和实践提供了丰富的资源。" 这个摘要涵盖了单调多边形三角剖分的算法原理、时间复杂度分析，以及计算几何领域的一般背景和相关知识，展示了这个主题在更广阔计算几何理论中的位置。