基于有序点列的平面点集凸包的新算法

作者：陈平; 汪国昭

来源：科技通报, 2007, 23(6): 863-866.

DOI：10.3969/j.issn.1001-7119.2007.06.019

• 平面点集
• 凸包
• 有序点列
• 极值点

提出了一种基于有序简单多边形的平面点集凸包快速求取的改进算法,新的算法能够避免极值点重合的问题.本文算法不仅达到了O(nlnn)的理论时间复杂度下限,而且算法简单,易于实现.

• 单位
  浙江大学