Two-dimensional closest pair problem: a closer look
type: Item
instance of: scholarly article
title: Two-dimensional closest pair problem: a closer look
zbMATH Open document ID: 1458.68265
author: Ovidiu Daescu
author: Ka Yaw Teo
published in: Discrete Applied Mathematics
publication date: 2020-10-14T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 7260821
zbMATH Keywords: closest pair
zbMATH Keywords: two dimensions
zbMATH Keywords: geometric bound
reviewed by: Krzysztof Gdawiec
MaRDI profile type: Publication
full work available at URL: j.dam.2020.08.006
OpenAlex ID: W3080461791
cites work: Q4140384
cites work: Q3651735
cites work: An improved algorithm for finding the closest pair of points
cites work: An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case
cites work: Q3992847
DOI: 10.1016/J.DAM.2020.08.006
Recommended article: Automata, Languages and Programming
Recommended article: On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Recommended article: A new algorithm for finding closest pair of vectors (extended abstract)
Recommended article: An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case
Recommended article: A note concerning the closest point pair algorithm.
Recommended article: Q4393381
Recommended article: The Closest Pair Problem under the Hamming Metric
Recommended article: Q4230362
Recommended article: A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
description: scientific article; zbMATH DE number 7260821