D. Proximity Graph
数学大学
D. Proximity Graph
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
D. Proximity Graph
计算几何 · 05. Delaunay Triangulation
Gabriel Graph
Gabriel 图：两点为直径的圆内不含其他点时连边——比 Delaunay 更稀疏。
定义
以 ab 为直径的圆为空 ⇒ 连边 ab
层次
Gabriel ⊆ Delaunay ⊆ 完全图
Relative Neighborhood Gr
相对邻域图（RNG）：不存在比两端都更近的第三点时连边。
定义
月牙形区域为空 ⇒ 连边
层次
RNG ⊆ Gabriel ⊆ Delaunay，逐层更稀
Lower Bounds
邻近图的构造下界与包含关系：越稀疏的图越省边、越少连通保证。
包含链
MST ⊆ RNG ⊆ Gabriel ⊆ Delaunay
用途
按连通与稀疏需求选层
本节要点
- ✓Gabriel：直径圆为空
- ✓RNG：月牙区为空，更稀疏
- ✓包含链：MST ⊆ RNG ⊆ Gabriel ⊆ Delaunay
延伸主题：验证一个点集的三层图比较各层的边数差异
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1这条包含链为什么对工程选择很有用？
参考答案不同应用需要不同稀疏度：路径规划要连通（MST 层），形状重建要饱满（Delaunay 层）。由于层层包含，可以先建最丰的 Delaunay，再按需抽取子集——一次计算、多层复用。
2Gabriel 图与 RNG 的边判定在实现上有什么差别？
参考答案Gabriel 检查「以边为直径的圆」内是否有点——圆的判定用点到圆心距离与半径比较；RNG 检查「月牙区」内是否有点——即同时距两端都更近。RNG 的月牙更小，所以边更少。
3三层图（Delaunay/Gabriel/RNG）分别适合哪些应用？
参考答案Delaunay 层最饱满，适合网格生成与插值；Gabriel 层适中的邻接骨架，用于聚类与模式分析；RNG 最稀疏，适合最小连接网络与形状重构的骨架提取。