并行与分布式系统中的并行Delaunay三角剖分：基于分治与合并的并行化算法（Parallel Delaunay Triangulation via Divide and Conquer）

题目描述

给定二维平面上的一组点集 \(P = \{p_1, p_2, ..., p_n\}\)，Delaunay三角剖分的目标是构造一个三角形网格，使得：

1. 所有三角形的顶点都来自点集 \(P\)。
2. 任意两个三角形不重叠，且所有三角形的并集覆盖点集的凸包。
3. 满足Delaunay性质：每个三角形的外接圆内部不包含点集中的其他点（空圆性质）。

并行Delaunay三角剖分算法要求利用多核或分布式环境，高效地计算点集的三角剖分，并保证结果的正确性与Delaunay性质。

解题过程循序渐进讲解

1. 理解Delaunay三角剖分的基本概念

• 三角剖分：将平面点集连接成互不重叠的三角形，覆盖点集的凸包。
• Delaunay性质：任意三角形的外接圆内不包含其他点。该性质最大化最小内角，避免出现“瘦长”三角形，在图形学和有限元分析中很重要。
• 应用场景：地理信息系统、有限元网格生成、三维重建、路径规划等。

2. 串行分治算法回顾

串行分治Delaunay三角剖分（如Lee & Schachter算法）步骤：

1. 排序点集：将所有点按x坐标排序（x相同则按y排序）。
2. 递归划分：将排序后的点集分成两个大小近似的子集（左半和右半）。
3. 递归计算：分别计算左半和右半子集的Delaunay三角剖分。
4. 合并剖分：合并左右两个Delaunay三角剖分，通过构造下凸包链和上凸包链，逐步添加边并调整以满足空圆性质（使用边缘翻转操作）。
5. 递归终止：当子集中点数 ≤ 3时，直接构造三角剖分。

关键操作：

• 合并：找到左右剖分的“连接边”，沿凸包逐步向上合并，检查空圆条件，若不满足则翻转边（类似Lawson的局部优化过程）。

3. 并行化挑战

• 数据依赖：分治合并过程中，左右子问题的合并需要同步，且合并顺序影响效率。
• 负载均衡：点集划分可能不均匀，导致子问题大小差异。
• 合并阶段串行瓶颈：传统分治合并是自底向上串行的。

4. 并行分治策略

我们采用并行递归分治与并行合并相结合的方法。

步骤1：并行排序与划分

• 使用并行排序算法（如并行快速排序或并行样本排序）将点集按x坐标排序。
• 将排序后的点集均匀划分成 \(t\) 个子集（\(t\) 为处理器数或线程数），每个子集分配给一个处理器。

步骤2：并行递归计算局部Delaunay剖分

• 每个处理器递归地对分配给它的子集进行Delaunay三角剖分（使用串行分治算法）。
• 递归过程中，若子集大小小于阈值（如 ≤ 1000点），则直接使用串行算法（如增量插入法）计算。
• 注意：每个处理器的计算完全独立，无需通信。

步骤3：并行合并相邻剖分

• 合并过程类似于归并排序的合并阶段，但需要处理几何约束。
• 两两合并：将相邻的两个Delaunay剖分合并成一个更大的剖分。合并操作可以并行进行，只要两个剖分不相交（即数据独立）。
• 合并树：构造一棵二叉树，叶子节点是各处理器的局部剖分，内部节点表示合并后的剖分。从叶子到根，每一层可以并行合并。

具体合并算法（并行化边缘翻转）：

1. 找连接边：对于两个相邻剖分 \(T_L\) 和 \(T_R\)，找到它们的凸包之间的两条公切线（上公切线和下公切线），形成一条“连接边”。
2. 构造初始合并链：从连接边开始，向上和向下逐步添加边，形成合并链。
3. 并行边缘翻转：
   • 将合并链上的每条边视为一个“待检查边”。
   • 检查是否满足空圆性质：对于两个共享边的三角形，检查对顶点是否在另一个三角形的外接圆内。
   • 若不满足，则翻转边（删除当前边，连接两个对顶点）。
   • 翻转可能影响邻近边，因此需要迭代进行直到所有边都满足Delaunay性质。
   • 并行化关键：将合并链划分成若干段，每段分配给不同处理器。处理器在段内局部进行边缘翻转，边界处需要同步（通过锁或原子操作避免冲突）。

步骤4：全局同步与后处理

• 所有合并完成后，得到全局Delaunay三角剖分。
• 可能需要移除凸包外的“无限三角形”（如果算法中添加了虚拟边界点）。
• 验证结果：可选步骤，检查所有三角形是否满足空圆性质。

5. 算法伪代码

输入：点集 P
输出：Delaunay三角剖分 T

1. 并行排序 P 按 x 坐标
2. 划分 P 为 t 个子集 P1, P2, ..., Pt
3. 并行 for i = 1 to t:
       Ti = DelaunayDivideConquer(Pi)   // 串行分治算法
4. 构建合并树，树高为 log t
5. for level = 0 to log t - 1:
       并行合并同一层中相邻的剖分对 (T2j, T2j+1) -> Tj'
6. T = 根节点的剖分
7. 返回 T

合并函数伪代码：

MergeDelaunay(TL, TR):
   1. 找到上下公切线，确定连接边 e0
   2. 从 e0 开始，向上构造合并链 L_up，向下构造合并链 L_down
   3. 将 L_up 和 L_down 划分成 k 段（k = 处理器数）
   4. 并行 for each segment:
          对段内的每条边执行局部边缘翻转直到稳定（满足空圆性质）
          边界边需同步处理（使用锁或原子操作）
   5. 返回合并后的三角剖分

6. 复杂度分析

• 时间：
  • 排序：\(O(n \log n)\) 并行时间（使用并行排序）。
  • 局部剖分：\(O(n \log n)\) 总工作量，但并行后每个处理器 \(O((n/t) \log (n/t))\)。
  • 合并：每层合并需要 \(O(n)\) 工作量（边缘翻转次数线性），树高 \(O(\log t)\)，总并行时间 \(O((n/t) \log t)\)（理想情况）。
• 空间：\(O(n)\)，存储三角剖分边和点。
• 通信：仅在合并阶段需要相邻处理器交换边界信息（凸包和连接边）。

7. 实际优化考虑

• 负载均衡：使用动态任务调度（如工作窃取）处理不均匀的子问题。
• 边界处理：合并时只交换凸包信息，减少通信量。
• 增量合并：可以采用流水线方式，一旦两个相邻剖分完成就立即合并，而不是等待整层完成。
• 容错：在分布式环境中，可使用检查点机制备份中间结果。

8. 总结

并行Delaunay三角剖分通过分治策略的并行化和合并阶段的并行边缘翻转，将计算分布到多个处理器。关键点在于：

• 并行排序与划分保证数据局部性。
• 独立计算局部剖分避免早期通信。
• 合并阶段采用分段并行翻转，减少同步开销。
  该算法适用于大规模点集，在GIS和科学计算中能显著加速网格生成过程。