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

An Efficient Approximation for Point Set Diameter in Two Dimension and its Generalization

提出一个计算平面数据直径的快速近似算法,其时间复杂度为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).