G. Minimum Weighted Triangulation
数学大学
G. Minimum Weighted Tria
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
G. Minimum Weighted Tria
计算几何 · 05. Delaunay Triangulation
Definition
最小权三角化：点集的所有三角剖分中，边权总和最小的那一个。
目标
最小化剖分中全部边（含边界）的长度和
对比
最大最小角是 Delaunay 的目标，这里是最小总权
Counter-Example
反例：最小权三角化不满足空圆性质——它不是 Delaunay 剖分。
构造反例
存在点集使 MWT 与 Delaunay 剖分不同
含义
两种「最优」的目标函数不同，互不蕴含
Hardness
最小权三角化是 NP 难的：不存在已知的多项式时间精确算法。
难度
比 Delaunay（O(n log n)）难得多
实践
用动态规划近似子结构或启发式
本节要点
- ✓MWT：边权和最小的三角剖分
- ✓MWT 不等于 Delaunay
- ✓MWT 是 NP 难的
延伸主题：构造一个 MWT ≠ Delaunay 的例尝试动态规划近似
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么 Delaunay 剖分 O(n log n) 可解，MWT 却是 NP 难？
参考答案Delaunay 有局部判据（空圆）支撑的贪心与分治结构；MWT 的目标是全局边权和最小，缺乏局部可分解的选择依据——决策相互纠缠，只能靠动态规划近似或指数枚举。目标函数的可分解性决定难度。
2最小权三角化的动态规划为什么一般不可行？
参考答案MWT 缺少「按顶点序切割」的天然子结构——最优剖分的子三角形可以跨越任意区域，区间 DP 的状态数爆炸。这与其 NP 难度一致，只能靠近似或限制输入（如凸多边形）。
3凸多边形的 MWT 为什么可以多项式求解？
参考答案凸多边形的三角剖分具有区间 DP 结构：按顶点序划分，状态 (i,j) 表示子多边形 i..j 的最优剖分，转移枚举第三个顶点 k。O(n³) 动态规划即可，凸多边形是 MWT 的可解特例。