We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 27 Issue 4
July  2012
Turn off MathJax
Article Contents
Abstract
References
Related Articles
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
shu

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

  • Department of Electronics and Computer Science, University of Algarve, Campus de Gambelas, 8005-139 Faro, Portugal Center for Environmental and Sustainability Research, Campus de Caparica, 2829-516 Caparica, Portugal

More Information
  • Received Date: October 14, 2011
  • Revised Date: April 07, 2012
  • Published Date: July 04, 2012
    Abstract
  • 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.
    • FullText(HTML)
    • References (8)
  • [1]
    Bentley J L. Multidimensional divide-and-conquer. Communicationsof the ACM, 1980, 23(4): 214-229.
    [2]
    Smid M. Closest-point problems in computational geometry.In Handbook of Computational Geometry, Sack J R, Urutia J(eds.), Amsterdam: Elsevier Science, 2000, pp.877-935.
    [3]
    Shamos M I. Geometric complexity. In Proc. the 7th Symp.Theory of Computing, New York, USA, May 1975, pp.224-233.
    [4]
    Bentley J L, Shamos M I. Divide-and-conquer in multidimensionalspace. In Proc. the 8th Symp. Theory of Computing,New York, USA, May 1976, pp.220-230.
    [5]
    Kleinberg J, Tardos E. Algorithm Design. Boston, USA:Addison-Wesley, 2005, pp.225-231.
    [6]
    Cormen T H, Leiserson C E, Rivest R L, Stein C. Introductionto Algorithms (2nd edition). Cambridge, USA: MIT Press,2001, pp.957-962.
    [7]
    Jiang M, Gillespie J. Engineering the divide-and-conquer closestpair algorithm. Journal of Computer Science and Technology,2007, 22(4): 532-540.
    [8]
    Ge Q, Wang H, Zhu Hong. An improved algorithm for findingthe closest pair of points. Journal of computer Science andTechnology, 2006, 21(1): 27-31.
    • Relative Articles

  • Related Articles

    [1]Minghui Jiang, Joel Gillespie. Engineering the Divide-and-Conquer Closest Pair Algorithm[J]. Journal of Computer Science and Technology, 2007, 22(4): 532-540.
    [2]Qi Ge, Hai-Tao Wang, Hong Zhu. An Improved Algorithm for Finding the Closest Pair of Points[J]. Journal of Computer Science and Technology, 2006, 21(1): 27-31.
    [3]Wu Jigang, Zhu Hong. The Least Basic Operations on Heap and Improved Heapsort[J]. Journal of Computer Science and Technology, 1994, 9(3): 261-266.
    [4]Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
    [5]I.V.Vel bitsky, A.L.Kovalev, I.V.Kasatkina, Wang Lei. R-Technology of Programming: Basic Notions and Implementation[J]. Journal of Computer Science and Technology, 1992, 7(4): 345-355.
    [6]Huang Wenqi, Wang Gangqiang. A Basic Algorithm for Computer-Aided Design of Material Arrangement[J]. Journal of Computer Science and Technology, 1992, 7(1): 56-61.
    [7]Liu Zhuojun. Processing Polynomial Algebraic Problems by Using SAC-2/ALDES[J]. Journal of Computer Science and Technology, 1991, 6(2): 195-200.
    [8]Zhu Xinjie. On the Structure of Binary Feedforward Inverses with Delay 2[J]. Journal of Computer Science and Technology, 1989, 4(2): 163-171.
    [9]Li Wanxue. Almost Optimal Dynamic 2-3 Trees[J]. Journal of Computer Science and Technology, 1986, 1(2): 60-71.
    [10]Li Wei. A Structural Operational Semantics for an Edison Like Language(2)[J]. Journal of Computer Science and Technology, 1986, 1(2): 42-53.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (35) PDF downloads (1721) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return