CS CG
前言
每个章节都由一个问题开始，用于解决这个几何问题的概念和技巧就是这个章节真正的主题。给出应用的目的是给予读者启发。
目录
- 计算几何-简介
- 线段相交-主题图叠加
- 多边形三角测量-守护一个艺术展览
- 线性规划-利用模具制造
- 垂直范围搜索-查询数据库
- 点的位置-知道你在哪
- Voronoi 图-邮局问题
- 安排与二元性-光线追踪中的超采样
- Delaunay 三角测量-高度插值
- 更多几何数据结构-窗口
- 凸包-杂项
- 二元空间划分-画家的算法
- 机器人运动规划-到你想到的地方
- 四叉树-非均匀网络生成
- 可见图-找到最短路径
- 单纯范围搜索-再看窗口
第一章：计算几何-简介 Computational Geometry - Introduction
三个例子：
- 走在大学里，有很多电话亭，你想找到最近的一个，拿到一张平面地图，可以利用 Voronoi 图将其划分；
- 知道要去哪个电话亭了，但是中间有建筑物障碍，拿到一张地图，但这时候需要让一个机器人利用程序去绕着障碍物走最短路；
- 获得了两张地图，一个是建筑物图，一个是道路图，你需要将他们叠在一起（Overlay），来展示两个图之间的组合信息。
1.1 简单例子：凸包 - Convex Hulls
对于几何背景的算法问题，好的方案通常有两个要素：其几何性质和算法技巧，二者缺一不可。
关于二维凸包问题，至少我还算了解，其定义就是给定平面上的点集 $P = {p_1, p_2, \cdots, p_n}$，计算一个点集，能包含所有点，以顺时针输出，称其为凸包。
作者给出的第一个 SlowConvexHull(P) 确实有点蠢（甚至比我想的最笨的方法还要笨），先枚举任意两点 $p,q$ 形成的边 $\overrightarrow{pq}$，然后对于每个边，如果剩下的任意点 $r$ 都在这个边的右边，那么这个边就是凸包的一个边。很明显，这个算法是 $O(n^3)$ 的。
而且，我们在这个算法里还需要考虑，如果 $r$ 在边 $\overrightarrow{pq}$ 之上（lies on），我们该怎么做呢？这就是一个经典的退化情况。我们一般来说在一开始思考几何问题的时候会忽略这些问题，但是在实际情况下一定要引起重视（打 ACM 天天遇到 corner case）。针对上面这个算法，我们把边的判定条件改成“$r$ 在边的右边或在边上”即可。
同时，我们还忽略了精度问题，简单地认为我们可以 somehow 准确判断一个点在一条边的左边或者右边，但如果点是以浮点坐标展现，实际上用浮 点计算的时候会出现误差导致误判。
尽管我们已经证明了算法的正确性，以及处理特殊情况，但是它仍然不具有鲁棒性，小的计算错误可能会导致它以完全意想不到的方式失败。
鲁棒性 Robustness：健全的，耐用的。
然后作者又提出了一种求凸包的算法，说实话这个方法是我当时第一次听到凸包这个概念时，想的类似方法。就是先把所有点按 x 轴排序，然后从最左边开始加点，每次加一个点，然后判断当前最尾端的三个点是否形成一个“右转”的折线，没有形成的话就删掉三个点中间的点。这样下来能找到整个凸包的上凸壳，再通过类似的算法找个下凸壳就好了。
这个算法里，每个点最多入队一次，出队一次，所以后面的部分复杂度是 $O(n)$
的，但是第一步排序的复杂度是 $O(n \log n)$ 的，所以还是一个 $O(n \log n)$ 的算法。
这个跟传统教的分治思想求凸包还不太一样，但其算法时间复杂度都是 $O(n \log n)$。
思考：能否用数学严谨证明求凸包算法的时间复杂度下限就是 $O(n \log n)$？
答案：可以，通过构造抛物线，将排序问题归约到凸包问题，已知排序问题下限是 $\Omega(n \log n)$。
退化和鲁棒性 Degeneracies and Robustness
一个计算几何算法通常有三个步骤：
- 忽略会影响几何概念的任何事情，尝试设计或理解一个算法；
- 调整算法设计来应对退化情况，例如用字典序等来处理某些情况，还有一个常用技巧是符号扰动；
- 实际实现，需要考虑到鲁棒性。
符号扰动 symbolic perturbation schemes：想象把输入点移动一个无限小的距离，使它们不再退化，但实际上不真正修改坐标，例如将 $x_i$ 变成 $x_i’ = x_i + \varepsilon_i$