• Articles • Previous Articles     Next Articles

Engineering the Divide-and-Conquer Closest Pair Algorithm

Minghui Jiang and Joel Gillespie   

  1. Department of Computer Science, Utah State University, Logan, Utah 84322-4205, U.S.A.
  • Received:2006-09-28 Revised:2007-05-08 Online:2007-07-10 Published:2007-07-10

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For $n$ points on the plane, our algorithm keeps the optimal $O(n \log n)$ time complexity and, using a circle-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 studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.

Key words: automatic algorithm design; algebraic specification; object-oriented methodology;

[1] Franco P Preparata, Michael Ian Shamos. Computational Geometry: An Introduction. Springer, 1985.

[2] Michael Ian Shamos. Geometric complexity. In -\it Proc. the 7th Annual ACM Symposium on Theory of Computing $($STOC'75$)$}, Albuquerque, NM, USA, 1975, pp.224$\sim$233.

[3] Michael Ian Shamos, Dan Hoey. Closest-point problems. In -\it Proc. the 16th IEEE Annual Symposium on Foundations of Computer Science $($FOCS'75$)$}, Los Alamitos, USA, 1975, pp.151$\sim$162.

[4] Michiel Smid. Closest-Point Problems in Computational Geometry. Handbook on Computational Geometry, Sack J R, Urrutia J (eds.), Elsevier Science, 2000.

[5] Jon Louis Bentley, Michael Ian Shamos. Divide-and-conquer in multidimensional space. In -\it Proc. the 8th Annual ACM Symposium on Theory of Computing $($STOC'76$)$}, Hershey, PA, USA, 1976, pp.220$\sim$230.

[6] Jon Louis Bentley. Multidimensional divide-and-conquer. -\it Communications of the ACM}, 1980, 23(4): 214$\sim$229.

[7] Michael Ben-Or. Lower bounds for algebraic computation trees. In -\it Proc. the 15th Annual ACM Symposium on Theory of Computing $($STOC'83$)$}, Boston, MA, USA, 1983, pp.80$\sim$86.

[8] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest \it et al. \rm Introduction to Algorithms. Second Edition, MIT Press, 2001.

[9] Gianni Franceschini, Viliam Geffert. An in-place sorting with $O(n\log n)$ comparisons and $O(n)$ moves. In -\it Proc. the 44th Annual IEEE Symposium on Foundations of Computer Science $($FOCS'03$)$}, Cambridge, MA, USA, 2003, pp.242$\sim$250.

[10] Yulin Zhou, Pengrong Xiong, Hong Zhu. An improved algorithm about the closest pair of points on plane set. -\it Journal of Computer Research and Development}, 1998, 35(10): 957$\sim$960. (in Chinese)

[11] Qi Ge, Hai-Tao Wang, Hong Zhu. An improved algorithm for finding the closest pair of points. -\it Journal of Computer Science and Technology}, 2006, 21(1): 27$\sim$31.

[12] David S Johnson. A theoretician's guide to the experimental analysis of algorithms. In -\it Proc. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges}, Michael H Goldwasser, David S Johnson, Catherine C McGeoch (eds.), DIMACS Monographs, Vol. 59, MAA Press, 2002, pp.215$\sim$250.

[13] Catherine C McGeoch. A bibliography of algorithm experimentation. In -\it Proc. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges}, Michael H Goldwasser, David S Johnson, Catherine C McGeoch (eds.), DIMACS Monographs, Vol. 59, MAA Press, 2002.

[14] Catherine C McGeoch, Bernard M E Moret. How to present a paper on experimental work with algorithms. -\it SIGACT News}, 1999, 30(4): 85$\sim$90.

[15] Intel x86 Instruction Set. http://www.intel.com/.

[16] Erich Friedman. Circles in circles. http://www.ste\-tson.edu/$\sim$efri\-edma/cirincir/.

[17] Eric W Weisstein. Circle packing. -MathWorld --A Wolfram Web Resource}, http://mathworld.wolfram.com/Circle\-Packing.html.

[18] Robert Sedgewick. -Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching}. 3rd Edition, Addison-Wesley, 1998.

[19] Jon Louis Bentley, M Douglas McIlroy. Engineering a sort function. -\it Software: Practice and Experience}, 1993, 23(11): 1249$\sim$1265.
[1] LUAN Shangmin; LI wei;. An Incremental Approach toAutomatic Algorithm Design [J]. , 1999, 14(4): 314-319.
Full text



[1] Hao Ruibing; Wu Jianping;. A Formal Approach to Protocol Interoperability Testing[J]. , 1998, 13(1): 79 -90 .
[2] Chen Gang;. Dependent Type System with Subtyping (I)Type Level Transitivity Elimination[J]. , 1998, 13(6): 564 -578 .
[3] SUN Ninghui;. Reference Implementation of Scalable I/O Low-Level API on Intel Paragon[J]. , 1999, 14(3): 206 -223 .
[4] Ying-Lei Song, Ji-Zhen Zhao, Chun-Mei Liu, Kan Liu, Russell Malmberg, and Li-Ming Cai. RNA Structural Homology Search with a Succinct Stochastic Grammar Model[J]. , 2005, 20(4): 454 -464 .
[5] Shan Wang, Xiao-Yong Du, Xiao-Feng Meng, and Hong Chen. Database Research: Achievements and Challenges[J]. , 2006, 21(5): 823 -837 .
[6] Qing Ai, Yan-Song Li, and Gui-Lu Long. Influences of Gate Operation Errors in the Quantum Counting Algorithm[J]. , 2006, 21(6): 927 -931 .
[7] Ji-Dong Chen and Xiao-Feng Meng. Indexing Future Trajectories of Moving Objects in a Constrained Network[J]. , 2007, 22(2): 245 -251 .
[8] Xue-Gang Hu, Pei-Pei Li, Xin-Dong Wu, and Gong-Qing Wu. A semi-random multiple decision-tree algorithm for mining data streams[J]. , 2007, 22(5): 711 -724 .
[9] Xiao-Min Hu, Jun Zhang, and Yun Li. Orthogonal Methods Based Ant Colony Search for Solving Continuous Optimization Problems[J]. , 2008, 23(1): 2 -0 .
[10] Yueh-Yi Lai and Wen-Kai Tai. Transition Texture Synthesis[J]. , 2008, 23(2): 280 -289 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved