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

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