A progressive algorithm for the closest pair problem. Issue 2 (3rd April 2021)

• Record Type: Journal Article
• Authors: Mesrikhani, Amir; Farshi, Mohammad; Iranfar, Behnam
• Is Part Of: International journal of computer mathematics. Volume 6:Issue 2(2021)
• Page Start: 130
• Page End: 136
• Publication Date: 2021-04-03
• Subjects: Progressive algorithms -- partial solutions -- the closest pair problem -- maximum pairwise distance -- minimum pairwise distance; 68Q25; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1862302
• Languages: English
• ISSNs: 2379-9927

Abstract

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 ( α 2 r ), where α is the ratio of the maximum pairwise distance and the minimum pairwise distance of points.