An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case

• DOI: 10.48550/arxiv.1010.5908
• Publication Date: 2010-01-01
• Authors: José Costa Pereira; Fernando G. Lobo
• Keywords: Computational Geometry (cs.CG); FOS: Computer and information sciences; F.2; Computer Science - Computational Geometry

We present an engineered version of the divide-and-conquer algorithm for finding closest pair points, within a given set points in XY-plane. For this we show that only two pairwise comparisons are required combine step, each point lies 2 delta-wide vertical slab. The correctness is shown all Minkowski distances with p>=1. also empirically that, although time complexity still O(n lg n), reduction total number leads to significant execution time, inputs size sufficiently large.