一种栅格辅助的平面点集最小凸包生成算法

摘要：

针对平面点集的最小凸包生成问题,提出一种栅格辅助的算法,预先剔除那些不可能成为凸包顶点的点,从而提高算法效率,算法的时间复杂度可近似达到O(n),最坏时间复杂度与Graham扫描算法相同.试验表明,随着行列数的增加,计算效率先快速递增,随后逐渐减小;当栅格行列数取值为总点数的平方根时,别除比接近最大值,算法执行效率亦相对较高.

关键词：最小凸包、栅格化、算法

所属期刊栏目：35

分类号：P208(一般性问题)

资助基金：国家基础科学人才培养基金资助项目J0630535

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

页码：403-406