无处不在的小土-index

第一章.多边形的三角分割(Polygon Triangulation)

1.1 艺术画廊定理 (Art Gallery Theorems)	本节定义了多边形，从 Klee 提出的多边形覆盖问题，讨论了数学家们如何形式化的描述问题，提出假设并严格证明。通过 Fisk 的充分性证明引出了多边形的三角分割问题。
1.2 三角分割理论 (Triangulation: Theory)	本节我们将证明每个多边形都可以进行三角分割，还会介绍一些三角分割的基本性质。
1.3 多边形的面积 (Area of Polygon)	本节我们将要研究如何计算一个多边形的面积。虽然这个问题本身就很有趣，但是我们的目标是为计算半平面的包含关系、线段的交点、可见性关系做一些准备工作，为最终在1.6.5 节中引出三角分割算法打基础。
1.4 实现的问题 (Implementation Issues)	本节用双向循环链表表示多边形，并提供了计算多边形面积的 C 程序。我们用 C++ 实现了一遍 Polygon.hpp。
1.5 线段相交 (Segment Intersection)	本节重申了多边形对角线的定义，并给出判定两个线段是否相交的实现。参考 Euclidean2.hpp 中的函数 Intersect。
1.6 三角分割实现 (Triangulation: Implementation)	本节先介绍了如何判定一条线段是多边形的对角线，然后基于双耳定理实现了复杂度为 \(O(n^2)\) 的三角分割算法。参考 Polygon.hpp 中的成员函数 Diagnal 和 Triangulate。

第二章.多边形分割(Polygon Partitioning)

在本章中，我们将探讨其他类型的多边形分割。分割单调(monotone)多边形(2.1节)、梯形(trapezoids)(2.2节)、"单调山(monotone mountains)"(2.3节)以及凸(convex)多边形(2.5节)。我们的主要目的是加速上一章中介绍的三角剖分算法，但这些分割方法本身也具有广泛的应用和研究价值。凸多边形分割的一个应用是字符识别: 光学扫描的字符可以表示为多边形(有时带有多边形孔洞)，并被分割成多个凸多边形，然后将分割后的结构与形状数据库进行匹配，从而识别字符(Feng & Pavlidis 1975)。此外，由于许多计算在凸多边形上更容易，例如，计算与障碍物或光线的交点；计算到直线的距离；判断一个点是否在多边形内部。所以这些应用的第一步通常都是，将复杂形状分割成凸多边形。

本章没有实现什么算法，但是有些练习里会建议读者自行实现。

2.1 单调多边形分割 (Monotone Partitioning)	本节介绍了单调多边形的概念，并简单概述了一种对单调多边形进行三角分割的贪心算法，其时间复杂度为 \(O(n)\)。
2.2 梯形化 (Trapezoidalization)	本节介绍一种基于平面扫描的方法将多边形梯形化，以便快速的将多边形分割成单调多边形。配合上一些特殊的数据结构，其时间复杂度为 \(O(n\log n)\)。
2.3 单调山分割 (Partition into Monotone Mountains)	上节中描述的算法有一个更简单的变体。其思路仍然是从 \(P\) 的梯形化开始，将之分割成若干个更容易进行三角分割的部分，称之为单调山 monotone mountains。
2.4 线性时间三角化 (Linear-Time Triangulation)	本节介绍了三角化算法的发展过程，极简述了复杂度为 \(O(n)\) 但细节非常多的Chazelle's 算法，以及复杂度为 \(O(n \log^* n)\) 但实现简单的Seidel's算法。
2.5 凸分割 (Convex Partitioning)	所谓的凸分割是将多边形分割成若干个凸多边形，而不局限于三角形。本节介绍凸分割问题，简要讨论如何将多边形分割成尽可能少的凸块。

第三章.二维凸包(Convex Hulls in Two Dimensions)

凸包是计算几何中最常见的结构。它本身就很有用，在很多情况下可以作为工具来构建其他结构。从纯数学的角度看来，它也是一个简洁优美的对象，扮演着核心角色。它也是计算几何研究中的成功应用的案例。计算几何领域最早的论文就涉及凸包的计算，我们将在3.5节中讨论。之后，关于凸包的研究层出不穷，为大多数自然问题(natural problems)找到了最优算法。本章我们将探讨其中一小部分工作，并在练习(3.9节)中补充一些材料。在继续探讨几何之前，我们先举几个应用的例子:

避障 Collision avoidance。如果包裹机器人的凸包能够避开障碍物，那么机器人本身也能避开障碍物。由于规划凸机器人避开障碍物的路径比非凸机器人的要容易得多，因此凸包常用于路径规划。这将在8.4节中讨论。
Fitting ranges with a line. Finding a straight line that fits between a collection of data ranges maps to finding the convex region common to a collection of half-planes (O'Rourke 1981).
最小包围盒子 Smallest box。对于能够包含一个多边形的最小面积盒子，至少有一条边与该多边形的凸包齐平。因此在最小包围盒子算法的第一步就是计算凸包(Toussaint 1983b)。类似地，在空间中寻找包围物体的最小三维盒子也需要物体的凸包(O'Rourke 1985a)。
形状分析 Shape analysis。为了进行模式匹配，我们会通过"凸差数 Convex Deficiency Tree(CDT)"对形状进行分类。CDT 的结构依赖于凸包的计算。这将在练习 3.2.3[2] 中进行探讨。

凸包很重要，所以我们不仅要给出严谨的定义，更要有直观透彻的理解。平面上一个点集的凸包，可以想象成在每个点上顶一个钉子，然后用橡皮筋围着这些钉子，自然绷直之后的形状。三维空间中点集的凸包边界，可以想象成用保鲜膜紧紧包裹住这些点所形成的形状。本章将给出凸和凸包的详细定义，并致力于构建凸包的算法。

3.1 凸和凸包的定义 (Definitions of Convexity and Convex Hulls)	本节罗列了一系列关于凸和凸包的概念定义，并简单讨论了凸包算法的输出形式，以及极点(extreme points)的概念。
3.2 极点的朴素算法 (Naive Algorithms for Extreme Points)	本节介绍了两个速度很慢的算法，用于求取非极点(nonextreme points) 和极边(extreme edges)。它们将作为后续更快算法的参照。
3.3 包装礼物算法 (Gift Wrapping)	本节介绍的包装礼物(gift wrapping)算法，相比于上一节要快一点，而且输出的凸包顶点是排序的。
3.4 快速凸包算法 (QuickHull)	本节介绍了一个类似快排的递归算法 QuickHull，在最好的情况其时间复杂度是 \(O(n \log n)\)。但最坏情况下，其复杂度仍然是二次的。
3.5 Graham 算法 (Graham's Algorithm)	Graham 算法十分简洁，通过栈结构和排序，实现了复杂度为 \(O(n\log n)\) 的凸包算法。实际上 \(O(n \log n)\) 的复杂度源自于快排的复杂度，扫描过程的复杂度只有 \(O(n)\)。
3.6 下界 (Lower Bound)	本文通过问题规约的方法，讨论了凸包算法的下界 \(\Omega(n \log n)\)。
3.7 增量算法 (Incremental Algorithm)	本文介绍的增量算法可以方便的扩展到更高维的空间中。在最坏的情况下它的复杂度是 \(O(n^2)\) 的，但经过排序并合理安排搜索策略之后，其复杂度可以达到 \(O(n \log n)\)。
3.8 分治 (Divide and Conquer)	分治是一种常用的算法思想。本文介绍的分治算法，是目前已知唯一能够扩展到三维并达到渐近最优 \(O(n \log n)\) 时间复杂度的技术。
3.9 附加练习 (Additional Exercises)	本节就是一些思考题，没有什么算法要介绍的。

第四章.三维凸包(Convex Hulls in Three Dimensions)

本章关注构建三维空间点集凸包的算法(第4.2节)。我们还将涉及一些相关问题，多面体的性质(第4.1节)、如何表示多面体(第4.4节)，还会简单探索一下更高维度的多面体(第4.6节)。最后，将通过一系列练习来探讨几个相关主题(第4.7节)。本章的核心内容是全书中最复杂的代码实现：通过增量算法(Incremental Algorithm)构建三维凸包的代码(第4.3节)。

4.1 多面体 (Polyhedra)	本节给出了多面体的严格定义。证明了三维空间中只有 5 种正多面体，它们被称为柏拉图多面体。著名的欧拉公式描述了零亏格多面体的点、边、面的关系。
4.2 凸包算法 (Hull Algorithms)	本节将简单提一下三维空间中的包装礼物算法Gift Wrapping，并概述三维分治算法Divide and Conquer的总体思想。重点在于介绍本章关注的三维增量算法Incremental Algorithm的框架。
4.3 增量算法的实现 (Implementation of Incremental Algorithm)	尽管增量算法在概念上清晰明了，但实现并不简单。在本节中，我们将深入探讨一个完整的实现方案，这也是本书中最复杂的实现。上一节中省略的细节，本节将结合代码一一补充。
4.4 多面体边界的表示方法 (Polyhedral Boundary Representations)	本节介绍了三种更为复杂的多面体边界的表示方法。相比于上一节，这些方法不要求面是三角形。专门设计的数据结构可以描述顶点、边、面之间的拓扑关系。
4.5 随机增量算法 (Randomized Incremental Algorithm)	本节十分简要的介绍了一种基于冲突图 conflict graph 的随机增量算法，它的期望时间复杂度是 \(O(n\log n)\)。
4.6 更高维度 (Higher Dimensions)	尽管本书不会涉及三维以上的计算几何内容，但如果对这一富有成果且至关重要的领域只字不提，那未免有些失礼。本节将是我们向该方向致意。领会高维几何是一项智力挑战，读者在这里只能浅尝辄止。
4.7 附加练习 (Additional Exercises)	本节就是一些思考题，没有什么算法要介绍的。

第五章.维诺图(Voronoi Diagrams)

在本章中，我们将研究维诺图(Voronoi diagram)，这是一种几何结构，其重要性仅次于凸包。从某种意义上说，维诺图记录了关于一组点(或更一般的对象)邻近性的一切信息。而在实际应用中，我们经常确实需要了解邻近性的细节，比如谁离谁最近？谁离谁最远？等等。这一概念的历史已超过一个世纪， Dirichlet 在 1850 年，Voronoi 在 1908 年的一篇论文中都曾探讨过。

我们将通过一系列示例来引出讨论，然后详细探讨维诺图丰富结构的细节(见 5.2 节和 5.3 节)，然后深入算法(见 5.4 节)。最后，我们将在 5.7 节揭示维诺图与凸包之间美妙的联系。本章仅包含两段简短的代码，用于构建维诺图的对偶图(即Delaunary 三角分割)，位于 5.7.4 节。

5.1 应用预览 (Applications: Preview)	本节介绍了若干个维诺图的应用。没有什么数学定义、定理、算法需要介绍的。
5.2 定义和基本属性 (Definitions and Basic Properties)	本节给出了维诺图的定义，并且给出了两个、三个、四个站点时维诺图的示例。此外本节还讨论了维诺图的大小(虽然每个单词都认识，但是我并没有看懂)。
5.3 Delaunay 三角分割 (Delaunay Triangulations)	Delaunay 三角分割是维诺图的对偶图。本节罗列了一些关于 Delaunay 三角分割和维诺图的性质。
5.4 算法 (Algorithms)	本节将简要地考察四种维诺图的计算方法，重点在于 Fortune 的平面扫描算法，其最坏情况复杂度是 \(O(n \log n)\) 的。
5.5 应用细节 (Applications in Detail)	本节将讨论维诺图的五个应用，不过详细程度会有所不同: 最近邻、"胖"三角分割、最大空圆、最小生成树和旅行商路径。
5.6 中轴 (Medial Axis)	本节介绍一个从维诺图引申出来的概念——中轴。在多边形内部，如果一个点到边界上有不止一个最近的点，也就是说，它到边界上两个或多个点的距离相等，那么这个点就在中轴上。
5.7 与凸包的联系 (Connection to Convex Hulls)	本节介绍了 Delaunay 三角分割与凸包之间存在的一种美妙的几何关系。利用这种关系，可以通过三维凸包算法来计算二维站点的 Delaunay 三角分割，进而得到维诺图。
5.8 与排列的联系 (Connection to Arrangements)	实际上，也是可以直接从三维的抛物面获取维诺图的，详细的介绍要到(6.6节)。本节先简要介绍一下这种联系。

有几篇综述介绍了构建维诺图的算法: Aurenhammer(1991), Fortune(1992), Fortune (1997)。Okabe 等人(1992) 的著作既介绍了算法也讨论了应用。

第六章.排列(Arrangements)

直线和平面的排列是计算几何中第三个重要结构，其重要性不亚于凸包和维诺图。所谓的直线排列通常是指平面上的一组直线将平面划分成的网格结构。本章将阐述直线排列的基本原理，目标是概述要点，详细内容留给其他资料参考。本章不包含任何实现示例，并且由于其抽象程度较高，可能是本书中最具挑战性的章节。

6.1 介绍 (Introduction)	本节简要介绍了可见性图、消除隐藏面、空凸多边形、切割火腿三明治，四种直线排列的应用。更详细的介绍参见6.7节
6.2 排列的组合学 (Combinatorics of Arrangements)	本节证明了两个二维空间中关于直线排列的定理。其一，给出了 n 条直线的所有简单排列构成的顶点、边、面的数量公式。其二是界定了几何结构线性复杂度的区域定理。
6.3 增量算法 (Incremental Algorithm)	本节给出了构建直线排列的增量算法，平面上的 \(n\) 条直线的排列可以在 \(\Theta(n^2)\) 的时间和空间内构建。
6.4 三维及更高维空间 (Three and Higher Dimensions)	排列理论最优美的方面之一是，几乎每一个特征都能平滑地推广到更高维度。