离散几何（Discrete Geometry）是几何学的一个重要分支，研究离散对象（如点、线、面、多面体）的几何性质和组合结构。与连续几何（如微分几何、黎曼几何）不同，离散几何关注的是有限或可数几何对象的计数、位置关系和拓扑性质，是数学、计算机科学、图形学、机器人学等多个领域的理论基础。
离散几何的核心研究范畴包括以下四个主要方向：
研究凸集的性质、凸包构造、支撑函数、混合体积和曼格夫斯基问题。凸几何不仅是离散几何的核心分支，也是优化理论、数学经济学和数据分析的理论基础。
研究几何对象的计数、排列、覆盖、填塞问题，关注几何结构之间的组合关系。这包括埃尔迪什—塞凯赖什类型的极值问题、海利定理等核心结果。
研究几何问题的算法设计与复杂度分析，涵盖凸包算法、三角剖分、空间索引结构、碰撞检测、范围搜索等。计算几何是计算机科学中发展最迅速的分支之一，广泛应用于图形学、GIS、机器人等领域。
将微分几何的核心概念（曲率、切向量、梯度、拉普拉斯算子等）在离散网格上做保结构离散化。DDG 是近年来新兴的活跃领域，在计算机图形学、物理仿真、数值分析中发挥着越来越重要的作用。
离散几何的起源可以追溯到古代数学。古希腊数学家深入研究了五种正多面体（柏拉图立体），并给出严格的几何证明——正多面体只有五种：正四面体、正六面体、正八面体、正十二面体、正二十面体。欧几里得的《几何原本》中就包含了这些结论。
| 时间 | 人物 | 贡献 |
|---|---|---|
| 约公元前300年 | 欧几里得 | 《几何原本》中系统研究多面体 |
| 1752年 | 欧拉（Euler） | 提出凸多面体公式 V - E + F = 2 |
| 19世纪末 | 曼格夫斯基（Minkowski） | 创立几何数论，混合体积理论 |
| 1930年代 | 埃尔迪什（Erdős）、塞凯赖什（Szekeres） | 快乐结局问题 |
| 1950年代 | 哈德维格（Hadwiger） | 积分几何基本定理 |
| 1970年代 | 多布金（Dobkin）、什拉什（Shamos） | 计算几何诞生 |
| 1980年代后 | 德·贝尔格（de Berg）、欧洛克（O'Rourke）等 | 计算几何成为成熟学科 |
| 2000年代后 | 格兰佐（Grinzun）等 | 离散几何在图形学和深度学习中复兴 |
欧拉公式 V - E + F = 2 对凸多面体而言是最基本的拓扑不变量。它的推广形式（V - E + F = 2 - 2g，其中 g 为亏格）适用于任意可定向曲面上的多面体。这个公式最初看似简单，但它建立了离散几何领域"计数+拓扑"的研究范式的雏形。
Hugo 的思考：欧拉公式的离散版本不仅在纯数学中重要，在计算机图形学中更是网格质量的验证工具。例如在重建三角形网格或四边形网格时，我们可以通过欧拉公式快速验证网格的拓扑正确性。在项目调试中，我曾用这一公式检查过数以万计的 mesh 是否出现了拓扑错误（如孔洞、非流形边等）。
凸几何研究欧几里得空间中的凸集，是离散几何最核心的领域之一。
一个集合 K ⊆ ℝ^d 称为凸集，当且仅当对于任意 x, y ∈ K 和任意 t ∈ [0,1]，有 (1-t)x + ty ∈ K。简单说，集合中任意两点的连线段完全包含在集合中。
凸集的基本性质包括：
给定点集 S ⊆ ℝ^d，其凸包 conv(S) 是包含 S 的最小凸集。凸包的维基教科书定义为：S 中所有点的所有凸组合构成的集合。
计算凸包的各种算法：
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| Graham Scan | O(n log n) | O(n) | 最经典，使用极角排序 + 栈维护 |
| Andrew 算法 | O(n log n) | O(n) | 按 x/y 排序后分别构建上下凸包 |
| Jarvis March（Gift Wrapping） | O(nh) | O(h) | h 为凸包顶点数，适合 h 很小的场景 |
| Quickhull | O(n log n) 期望 | O(n) | 分治法，平均性能好，最坏 O(n²) |
| Chan 算法 | O(n log h) | O(n) | 最优输出敏感算法 |
| Kirkpatrick–Seidel | O(n log h) | O(n) | 理论上最优的分治算法 |
Hugo 的项目经验：在一个大规模空间聚类项目中，我实现了 Andrew 算法来处理数十亿条空间位置数据。关键挑战在于：标准实现假设所有数据在内存中可排序，但面对海量数据时，需要设计针对性的 external sort 策略。实际工程经验表明，如果数据分布存在偏斜（如某个区域高度聚集），凸包构造反而比预期更快，因为排序预处理可以提前排除大量内点。此外，对于流式数据场景，还可以使用有损近似算法（如 Douglas-Peucker 算法简化轨迹后再计算凸包）。
凸多面体是凸多边形在高维的推广。它有下面两种重要的等价描述：
这两种描述之间的转换是离散几何中的经典困难问题：
| 方向 | 算法 | 复杂度 |
|---|---|---|
| V → H（凸包面枚举） | Flip 算法、Buck's 算法 | 指数级 |
| H → V（顶点枚举） | 双重描述法（Double Description Method） | 指数级 |
应用：在控制系统理论中，凸多面体用于表示可达集（reachable set）；在经济学中，它们对应可行消费集合；在计算化学中，用于表示构象空间中的禁止区域。
高维凸多面体满足广义欧拉-庞加莱公式：
其中 f_k 是 k 维面的个数。对于三维多面体（d=3），这个公式简化为熟悉的 V - E + F = 2。
迪恩-索默维尔关系（Dehn-Sommerville Relations）进一步刻画了单纯凸多面体的面向量必须满足的线性等式，是理解多面体极值问题的基本工具。
曼格夫斯基证明了关于凸体表面积与支撑函数的深刻联系，并发展了混合体积（Mixed Volumes）理论。给定两个凸体 K 和 L，定义：
其中 V(K, L) 就是 K 和 L 的混合体积。混合体积理论是现代凸几何和代数几何（小平邦彦/Kawamata 一维）的基础之一。
对于欧几里得空间中的非空紧凸集 A, B：
等号成立当且仅当 A 和 B 是位似集（homothetic）。
这个定理的广泛应用包括：
在 ℝ^d 中，任何凸组合最多可以用 d+1 个点的凸组合来表示。这一定理是单纯形法的理论基础，也是维度约简的一个理论保证。它告诉我们，每个凸包中的点都可以用附近有限的顶点"代表"——这是压缩感知和稀疏表示的理论起点。
闵可夫斯基和（Minkowski Sum）定义为 A + B = {a+b | a∈A, b∈B}。在机器人学的配置空间中，障碍物的计算可以用闵可夫斯基和的变种（A ⊕ B 或 A ⊖ B）来表示。具体来说：
应用场景：
组合几何研究几何对象之间的组合与计数关系，是离散几何中最富有数学美感的领域之一。
这个定理的名字源于埃斯特·克莱因（Esther Klein）的婚礼派对场景。埃斯特·克莱因提出了如下问题：平面上任意五个点（无三点共线）中，能否总是包含一个凸四边形？答案是肯定的。
一般形式：对于任意整数 m ≥ 3，存在最小整数 N(m)，使得平面上任意 N(m) 个处于一般位置的点中，必然存在 m 个点构成一个凸 m 边形。
已知的精确值：
Hugo 的思考：这个看似纯粹的数学问题实际上与计算机科学中的数据排序和模式识别密切相关。可以从另一个角度看：给定任意顺序的一组点，如何保证存在一个"凸"的模式？这个问题在机器学习中的序列模式识别、时间序列的拐点检测等场景中都有类似的思想。
平面上 n 条线和 m 个点之间最多有 O(n^{2/3} m^{2/3} + n + m) 个重合（incidences）。即点和线产生的最多"关联对"数量。
这个定理是加性组合学（Additive Combinatorics）的基石：
Hugo 的实践经验：在分析碰撞检测算法性能时，Szemerédi–Trotter 定理提供了重要的理论指导——它指出空间中线与物体的相交次数存在一个紧密的上界，帮助我们理解为什么在工程实践中，基于空间分区的算法（如 BSP 树、四叉树）在最坏情况下仍能保持可接受的性能。
在 ℝ^d 中，任意一族凸集，如果其中任意 d+1 个都有非空交集，那么整个族就有非空交集。
推广形式：海利数（Helly number）的概念可以推广到更一般的拓扑结构上。例如在树的组合几何中，度量空间的海利数可能不同。
实际应用：
覆盖（Covering）和填塞（Packing）问题是组合几何中的经典研究主题：
球体填塞（Sphere Packing）：比如在三维空间中，最密的球填充密度是多少？开普勒猜想（Kepler Conjecture）认为面心立方（FCC）和六方最密堆积（HCP）的密度均为 π/(3√2) ≈ 0.74048。该猜想在 1998 年由海尔斯（Hales）借助计算机证明，花了近 400 年。
圆盘覆盖（Disk Covering）：用最少数量的等圆覆盖给定区域。这一问题在通信基站选址、传感器部署中有直接应用。
圆盘填塞/多边形填塞：
凯勒猜想（Keller's Conjecture）：用同样大小的超立方体填塞 ℝ^d，如果填入的立方体与坐标轴平行且放置在整数格点上，那么是否存在一个面到面的接触？Keller 猜想：在任何维度下都存在这样的接触。结果：
欧几里得拉姆齐理论（Euclidean Ramsey Theory）探索几何结构中的"不可避免的单色模式"：
范德瓦尔登定理（van der Waerden's Theorem）：将自然数用有限种颜色染色，必定存在任意长度的单色等差数列。几何版本涉及点的共线性问题。
海尔斯-朱伊特定理（Hales-Jewett Theorem）：任何有限维度正立方体在有限颜色染色后，必然存在一个单色"组合线"。
加莱-维特定理（Gallai-Witt Theorem）：任意有限维整数格子在有限颜色染色后，必然存在任意有限结构的单色仿射副本。这是范德瓦尔登定理的多维推广。
计算几何是离散几何与计算机科学的交叉学科，关注几何问题的有效算法设计与复杂度分析。它萌芽于 1970 年代，经过几十年的发展已成为一个成熟的学科。
最常用的二维凸包算法之一：
1. 将点按 x 坐标排序（x 相同时按 y 排序）
2. 构造下凸包：从左到右扫描，用栈维护凸包
3. 构造上凸包：从右到左扫描，用栈维护凸包
4. 合并上下凸包，移除重复端点
复杂度：O(n log n)，其中排序占主导。算法简洁、易于正确实现。代码实现不超过 50 行。
工程注意：精度处理——当使用浮点数时，需要容差比较；当使用整数 / 有理数时，需要处理共线点问题。CGAL 使用精确核（Exact Kernel）避免这些问题，但代价是更慢的速度。
Chan 算法（1996）达到了 O(n log h) 的理论最优复杂度，用巧妙的分治+二分策略避免了排序全部点的时间。算法核心思路：
德劳内三角剖分是平面点集的一个三角剖分，满足空外接圆条件：每个三角形的外接圆内不包含点集中的任何其他点。
重要性质：
算法：
| 算法 | 复杂度 | 特点 |
|---|---|---|
| Bowyer-Watson（增量法） | O(n²) | 最简单的实现 |
| 分治法 | O(n log n) | 效率高，实现复杂 |
| Fortune（扫描线） | O(n log n) | 基于转换到沃罗诺伊图 |
| Guibas-Stolfi | O(n log n) | 结合分治和扫描线 |
Hugo 的经验：Bowyer-Watson 算法虽然最坏 O(n²)，但实际应用中很少出现退化情况。我曾在空间插值项目中用它处理过 500 万个点，工程性能在可接受范围内（约 2 分钟完成）。如果追求生产性能，应选择分治法的 CGAL 实现。
沃罗诺伊图将空间划分为若干区域，每个区域属于离它最近的点（种子/站点）。对于从 P = {p₁, p₂, ..., pn} 构建的沃罗诺伊图：
算法：
应用：
| 结构 | 维度范围 | 查询类型 | 时间复杂度 | 工程适用性 |
|---|---|---|---|---|
| K-D 树 | 2-20 | 范围查询、NN | 平均 O(√n + k) | 静态数据友好，实现简单 |
| R 树（R* 树） | 2-50 | 范围查询、NN | O(√n + k) 平均 | 动态数据，PostGIS/SQLite 首选 |
| BSP 树 | 2-3 | 碰撞检测 | O(log n) 期望 | 游戏引擎中的标准做法 |
| 四叉树 / 八叉树 | 2-3 | 范围查询、碰撞 | O(n^{1-1/d}+k) | 均匀数据性能好 |
| 网格 / 哈希网格 | 任意 | 碰撞检测 | O(1) 期望 | 粒子系统、物理模拟 |
| 局部敏感哈希（LSH） | 高维 | 近似近邻 | 亚线性 | 高维数据的唯一选择 |
| VP 树 / BK 树 | 度量空间 | NN | O(log n) 期望 | 适用于任意度量空间 |
Hugo 的实践建议：
碰撞检测（Collision Detection）是计算几何在工程中最广泛的应用之一——从物理引擎中的刚体碰撞响应，到机器人避障，再到虚拟现实中的交互反馈，都离不开高效的碰撞检测。这也是游戏引擎中占用计算资源最多的模块之一。
为了高效处理大规模场景中的碰撞，工程上通常采用两阶段策略：
实际工程中的经验数据：在典型游戏场景中，宽相位可以过滤掉95%以上的不可能碰撞对。如果Bounding Sphere检测通过后，再用OBB（有向包围盒）进一步精化，可以大幅减少GJK等算法的调用次数。
简单多边形三角剖分（Triangulation of Simple Polygon）：
耳切法（Ear Clipping）：
单调多边形三角剖分：
离散微分几何（DDG）兴起于 2000 年代初，旨在将微分几何的连续概念离散化到三角网格上，同时保留连续情形下的重要结构性质（如谱性质、不变量）。
DDG 的核心方法论是"离散优先"（Discrete-first）：不把离散看做连续的近似，而是从离散开始定义正确的理论框架，使得连续情形是离散情形在网格精细化的极限。这种思想的优点是离散情形本身就保持了几何的不变量和对称性。
在三角网格上，有多种方式定义离散曲率：
离散高斯曲率（Gauss-Bonnet 的形式）：
其中 θ_i 是顶点 v 处相邻三角形的内角。网格总的高斯曲率之和等于 2πχ（χ 是欧拉示性数）——这是离散 Gauss-Bonnet 定理的直接推论。
离散平均曲率：
可以在每条边上定义，基于二面角（相邻面法向量之间的角度）：
其中 |e| 是边的长度，φ_e 是相邻面的二面角。
离散拉普拉斯-贝尔特拉米算子（Laplace-Beltrami Operator）是 DDG 中最重要的工具之一：
L 是一个 N×N 矩阵（N 为顶点数），定义为：
常用的权值定义包括：
余切权被广泛使用，因为它在网格细化下收敛到连续拉普拉斯算子。
应用场景：
Hugo 的个人心得：我研究 DDG 时受益于 Keenan Crane 教授的教学讲义。它的核心理念——尝试从离散出发定义量（而不是离散化连续公式）——对我思考计算机图形学中的许多问题产生了深远影响。例如，在处理三角网格的保角度映射（Conformal Mapping）时，DDG 方法通常比传统的有限差分法更稳定，因为它是"结构保持"的。
| 库名 | 语言 | 核心领域 | 许可证 | 难度 | 特色 |
|---|---|---|---|---|---|
| CGAL | C++ | 计算几何 | GPL/LGPL | 高 | 工业级精确几何，最长开发历史 |
| Boost.Geometry | C++ | 通用几何 | Boost | 中 | 与 STL 高度集成 |
| Triangle | C | 三角剖分 | 非商业 | 低 | Shewchuk 的经典库 |
| libigl | C++ | 图形学 | MPL 2.0 | 中 | 交互式几何处理框架 |
| Geogram | C++ | 数值几何 | BSD-3 | 中 | 大规模网格处理 |
| Shapely | Python | GIS | BSD-3 | 低 | Python 几何操作标准库 |
| PyMesh | Python | 网格处理 | MIT | 中 | 多功能网格处理 |
| scipy.spatial | Python | 几何计算 | BSD-3 | 低 | 包含 kd-tree, Delaunay, ConvexHull |
| Open3D | C++/Python | 3D 数据处理 | MIT | 中 | 点云 + 深度学习 |
| p2t (Poly2Tri) | C++/多种绑定 | 三角剖分 | BSD | 低 | 带孔洞多边形三角剖分 |
Hugo 的选择建议：
离散几何分析（Discrete Geometric Analysis）由 Kotani、Grigor'yan、Chung 等人的工作建立，将图上的谱理论、离散调和分析和组合几何统一在同一数学框架下。它利用离散拉普拉斯算子研究图和网络的几何性质，与机器学习中的图神经网络（GNN）在理论上直接相关。
随着神经网络在点云、网格、图结构数据上的应用爆发，离散几何为这些模型提供了数学基础：
当维度变得很高时，几何性质会发生反直觉的变化——这种现象被称为"维度灾难"（Curse of Dimensionality）的几何根源：
这些性质不仅解释了为什么某些算法（如K-D树）在高维失效，也启发了新的方法：
| 书名 | 作者 | 适合读者 | 内容侧重 |
|---|---|---|---|
| 《计算几何：算法与应用》 | de Berg 等 | 入门 | 算法实现，案例丰富 |
| 《离散几何》 | Jiří Matoušek | 中级 | 理论覆盖广 |
| 《Lectures on Discrete Geometry》 | Jiří Matoušek | 高级 | 研究生讲义 |
| 《Computational Geometry: Theory and Applications》 | 期刊 | 前沿 | 学术论文 |
| 《曲线与曲面的微分几何》 | do Carmo | 中级 | 微分几何基础 |
| 《离散微分几何》 | Crane 等 | 研究生 | 最新的讲义 |
| 《凸优化》 | Boyd | 中级 | 凸几何的优化应用 |
第一阶段（基础建设）：
第二阶段（能力提升）：
第三阶段（专精方向）：
离散几何作为数学与计算机科学的交叉桥梁，其重要性随着 AI 和数据科学的兴起与日俱增。从二维平面的简单几何问题，到高维空间的复杂结构分析，再到图神经网络的数学基础——离散几何提供了独特的分析和洞察视角。正如 Sharir 教授所说："离散几何研究离散的几何和连续的组合。"