Two-dimensional closest pair problem: a closer look (Q2004080)

The authors study the 2D closest pair problem, i.e., from given \(n\) 2D points, one wants to find the two closest ones using the Euclidean metric. The authors show that in the combine stage of the classical divide-and-conquer algorithm for solving this kind of problems, it is sufficient, and sometimes necessary, to check only the next three points following the current point in the \(y\)-sorted array. To show the performance of the proposed approach, the authors perform some numerical experiments and compare them with other known variants of the divide-and-conquer algorithms.