关于求平面点集凸包的一个O(n)时间算法的商榷

被引：7

作者：

刘金义

机构：

[1] 抚顺石油学院计算机科学与技术系

来源：

关键词：

计算几何; 点集; 凸包; 算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

王志强等于 1998年提出了一个计算平面点集凸包的新算法 ,并且声称该算法的最坏时间复杂度为 O(n) ,从而为线性时间排序提供了可能性 .该文对王志强等提出的求平面点集凸包算法的时间分析提出不同观点 ,进一步明确了平面点集凸包算法和排序算法的时间下界为 Ω(nlogn)

引用

页码：670 / 672

页数：3