确定平面点集凸包的一类最优算法

摘要

确定平面点集的凸包问题在计算机图形学、图象处理、VLSI设计与CAD/CAM等众多领域中有广泛的应用,多年来人们一直在寻找此问题的快速算法.本文研究了平面点集的凸包问题与排序问题的内在联系,证明了在最坏情况下这两个问题的最优算法具有相同的时间复杂度,进而将平面点集的凸包问题转化成排序问题,并利用双动线检测方法构造了以排序算法为基础的确定平面点集凸包的一类最优算法.