Two-dimensional closest pair problem: a closer look

DOI10.1016/J.DAM.2020.08.006MaRDI QIDQ2004080zbMATH OpenOpenAlexFDO

Authors Ovidiu Daescu, Ka Yaw Teo

Publication date 14 October 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.08.006

zbMATH Keywords

closest pairgeometric boundtwo dimensions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Automata, Languages and Programming
• On the complexity of closest pair via polar-pair of point-sets
• On the complexity of closest pair via polar-pair of point-sets
• A new algorithm for finding closest pair of vectors (extended abstract)
• An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case
• A note concerning the closest point pair algorithm.
• scientific article; zbMATH DE number 1161382
• The Closest Pair Problem under the Hamming Metric
• scientific article; zbMATH DE number 1256675
• A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES

Cites work

• An improved algorithm for finding the closest pair of points
• An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3569833 (Why is no real title available?)
• Introduction to algorithms.

Cited in

(5)

• An improved algorithm for finding the closest pair of points
• An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case
• A geometric algorithm based on dynamic rectangular window for closest points
• The average performance analysis of a closest‐pair algorithm
• scientific article; zbMATH DE number 1161382 (Why is no real title available?)

This page was built for publication: Two-dimensional closest pair problem: a closer look

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004080)