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 steps and spends
time in each step. In step r, the error of the partial solution is bounded by
, where α is the ratio of the maximum pairwise distance and the minimum pairwise distance of points.
2010 Mathematics Subject Classification:
Disclosure statement
No potential conflict of interest was reported by the author(s).