A progressive algorithm for the closest pair problem

Abstract

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(\log n)$ steps and spends $O(n)$ time in each step. In step r, the error of the partial solution is bounded by $O(\frac{\alpha }{2^r})$, where α is the ratio of the maximum pairwise distance and the minimum pairwise distance of points.

Keywords:

• Progressive algorithms
• partial solutions
• the closest pair problem
• maximum pairwise distance
• minimum pairwise distance

2010 Mathematics Subject Classification:

• 68Q25

Disclosure statement

No potential conflict of interest was reported by the author(s).