首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》相关算法

关灯直达底部

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

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