寻求简单多边形凸壳的线性时间算法

摘要：

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法.第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选,使剩余顶点的角的大小排成递增序,然后用Graham扫描方法删去非凸壳顶点,最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的凹点,最后得到凸壳顶点序列.这两种算法简单,易于实现,时间复杂性都是O(n).

关键词：多边形、凸壳、算法、复杂性

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1-2,44