相关算法

一旦得到一个凸包，那么使用Overmars和van Leeuwen（1981）的方法可以高效地维护这个凸包。这些点被存储在一个支持插入和删除的树结构中。插入或者删除的开销是O(log2n)，所以构建凸包的总开销是O(n log2n)，需要O(n)的空间。结果有力地支持了这样一种观点：性能的每次改善都来自于算法和实现自身的改进和平衡，而不是对数据有特定的要求。

最早计算凸包的一个算法叫做Graham扫描，这个算法在1972年提出，需要使用到简单的三角函数性质。使用图9-9检查右折的方法，一个恰当的实现只需要简单的数据结构和基本的数学计算。Graham扫描首先将所有的点按照和最左下方的点的夹角进行排序，它能在O(n log n)的时间内计算出凸包。需要注意的是夹角相同的点，其顺序是按照距离来决定的。