一种栅格辅助的平面点集最小凸包生成算法
针对平面点集的最小凸包生成问题,提出一种栅格辅助的算法,预先剔除那些不可能成为凸包顶点的点,从而提高算法效率,算法的时间复杂度可近似达到O(n),最坏时间复杂度与Graham扫描算法相同.试验表明,随着行列数的增加,计算效率先快速递增,随后逐渐减小;当栅格行列数取值为总点数的平方根时,别除比接近最大值,算法执行效率亦相对较高.
最小凸包、栅格化、算法
35
P208(一般性问题)
国家基础科学人才培养基金资助项目J0630535
2010-09-28(万方平台首次上网日期,不代表论文的发表时间)
403-406