{ 上一节介绍了凸包的高效算法 和一个最远点对的应用 这一段将更好的解决最远点对问题 } (若不做特殊说明 下文讨论的问题均是在欧氏空间  若不做特殊说明 下文中距离均是指空间中欧氏距离) ============================== 一.简单枚举算法的不足 上一次介绍了一个基本的求平面最远点对的算法 即先求点集的凸包 然后枚举凸包上的点来求最远点集 这是利用了凸包上的点

{ 承上一节 继续介绍点集的凸包  (下文中所有凸包 若不做特殊说明均指点集的凸包) 这一节介绍相比更高效的算法 } ==================================================================== 一.卷包裹算法(Gift Wrapping Algorithm)的特性 前面提到过卷包裹算法的复杂度问题 由于卷包裹算法是两重循环实现

{ 半个寒假都在写凸包 这几篇文章整理一下 主要介绍 二维凸包的求解算法 以及一个简单的应用 ｝ ==================================================================== 一.凸集&凸包 (下文中所有的集合 若不作特殊说明 都是指欧氏空间上的集合) 凸集(Convex Set):任意两点的连线都在这个集合内的集合就是一个凸集.