We use cookies to improve your experience with our site.
Minghui Jiang, Joel Gillespie. Engineering the Divide-and-Conquer Closest Pair Algorithm. Journal of Computer Science and Technology, 2007, 22(4): 532-540.
Citation: Minghui Jiang, Joel Gillespie. Engineering the Divide-and-Conquer Closest Pair Algorithm. Journal of Computer Science and Technology, 2007, 22(4): 532-540.

Engineering the Divide-and-Conquer Closest Pair Algorithm

  • We improve the famous divide-and-conquer algorithm by Bentley and Shamosfor the planar closest-pair problem. For n points on the plane, ouralgorithm keeps the optimal O(n \log n) time complexity and, using acircle-packing property, computes at most 7n/2 Euclidean distances,which improves Ge \it et al.'s bound of (3n\log n)/2 Euclidean distances.We present experimental results of our comparative studieson four different versions of the divide-and-conquer closest pair algorithmand propose two effective heuristics.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return