一种平面数据直径的快速近似算法及其推广

摘要：

提出一个计算平面数据直径的快速近似算法,其时间复杂度为O(N+1/ε).该算法和现有的近似算法结合可推广至高维情形,其时间复杂度为O(Nε-d-2/2+ε-d/2).同时,对Graham扫描法进行了改进,使总用时和内存消耗减少,算法的时间复杂度同样可达到理论下限O(N logN).

关键词：平面数据直径、近似算法、高维推广、计算几何

所属期刊栏目：9

分类号：O29(应用数学)

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

页数：共8页

页码：83-90