Two-dimensional closest pair problem: a closer look (Q2004080)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two-dimensional closest pair problem: a closer look |
scientific article |
Statements
Two-dimensional closest pair problem: a closer look (English)
0 references
14 October 2020
0 references
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.
0 references
closest pair
0 references
two dimensions
0 references
geometric bound
0 references
0 references