摘要
提出一个计算平面数据直径的快速近似算法,其时间复杂度为O(N+1/ε).该算法和现有的近似算法结合可推广至高维情形,其时间复杂度为O(Nε^-(d-2)/2+ε^-d/2).同时,对Graham扫描法进行了改进,使总用时和内存消耗减少,算法的时间复杂度同样可达到理论下限O(Nlog N).
This paper presents an algorithm to efficiently approximate the point set diameter in a plane with a time complexity of O(N+1/ε).The combination of this algorithm and the existing approximation algorithm for point set diameter can be applied to the approximation of point set diameter in higher dimensions with a time complexity of O(Nε-^(d-2)/2+ε-^d/2).Moreover,the method proposed in this paper reduces the time and memory consumption of the Graham′s Scan,and the time complexity of the improved Graham′s Scan also reaches the theoretical lower bound O(NlogN).
作者
林珈音
贾小芃
朱浩楠
LIN Jiayin;JIA Xiaopeng;ZHU Haonan(Beijing National Day School,Beijing 100039,China)
出处
《数学建模及其应用》
2020年第2期83-90,共8页
Mathematical Modeling and Its Applications
关键词
平面数据直径
近似算法
高维推广
计算几何
point set diameter in a plane
approximation algorithm
higher dimensional generalization
computational geometry