We use cookies to improve your experience with our site.
José C. Pereira, Fernando G. Lobo. An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case[J]. Journal of Computer Science and Technology, 2012, 27(4): 891-986. DOI: 10.1007/s11390-012-1272-6
Citation: José C. Pereira, Fernando G. Lobo. An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case[J]. Journal of Computer Science and Technology, 2012, 27(4): 891-986. DOI: 10.1007/s11390-012-1272-6

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

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

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return