文献类型：期刊文章

作　　者：刘润涛[1]

机构地区：[1]哈尔滨理工大学信息与科学计算技术研究所,哈尔滨150080

出　　处：《工程图学学报》

基　　金：国家自然科学基金资助项目(10171025)

年　　份：2002

卷　　号：23

期　　号：2

起止页码：120-126

语　　种：中文

收录情况：CSCD、CSCD_E2011_2012、JST、普通刊

摘　　要：给出了一个计算简单多边形凸包的新算法。其搜索策略为:对简单多边形上的点进行分类,排除不可能为凸包上的点,缩小搜索范围,从而降低算法的时间复杂度。该算法具有线性时间复杂度和空间复杂度。同时,具体量化了该算法的复杂度,给出了该算法的时间复杂度和空间复杂度的确定的上界,即,时间复杂度为不超过4(n-4)次乘法、6(n-4)次减法和17n-12次比较运算,空间复杂度为不超过2n个存储单元(n是该简单多边形顶点的个数)。

关 键 词：线性算法  简单多边形 凸包 计算几何  时间复杂度 空间复杂度

分 类 号：TP301.6] O18[计算机类]