A progressive algorithm for the closest pair problem
Amir Mesrikhani, Mohammad Farshi, Behnam Iranfar · International Journal of Computer Mathematics Computer Systems Theory · 2020
Developing algorithms that produce approximate solutions is always interesting when we are generating the final solution for a problem. Progressive algorithms report a partial solution to the user which approximates the final solution in some specific steps. Thus, the user can stop the algorithm if the error of the partial solution is tolerable in terms of the application. In this paper, we study the closest pair problem under the Euclidean metric. A progressive algorithm is designed for the closest pair problem, which consists of O(logn) steps and spends O(n) time in each step. In step r, the error of the partial solution is bounded by O(α2r), where α is the ratio of the maximum pairwise distance and the minimum pairwise distance of points.