Divide and conquer for the closest-pair problem revisited

References

• Bentley J. L. Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space Ph.D. Thesis, Department of Computer Science, University of North Carolina Chapel Hill NC 1976
   Google Scholar
• Bentley , J. L. 1980 . Multidimensional divide-and-conquer . Communications of the ACM , 23 : 214 – 229 .
   Web of Science ®Google Scholar
• Bentley , J. L. and Shamos , M. I. 1976 . Proc. 8th Annual ACM Symposium on Theory of Computing . Divide-and-conquer in multidimensional space . 1976 , Hershey, PA. pp. 220 – 230 .
   Google Scholar
• Bentley , J. L. and Shamos , M. I. 1978 . Divide and conquer for linear expected time . Information Processing Letters , 7 : 87 – 91 .
   Web of Science ®Google Scholar
• Chang , R. C. and Lee , R. C. T. 1984 . The average performance analysis of a closest-pair algorithm . International Journal of Computer Mathematics , 16 : 125 – 130 .
   Web of Science ®Google Scholar
• David , H. A. 1970 . Order Statistics , New York, , NY : Wiley .
   Google Scholar
• Devroye , L. 1986 . Lecture Notes on Bucket Algorithms , Boston, MA : Birkhauser .
   Google Scholar
• Fortune , S. and Hopcroft , J. 1979 . A note on Rabin's nearest-neighbor algorithm . Information Processing Letters , 8 : 20 – 23 .
   Web of Science ®Google Scholar
• Hinrichs , K. , Nievergelt , J. and Schorn , P. 1987 . Plane-sweep solves the closest pair problem elegantly , Chapel Hill, NC : University of North Carolina . Typescript, Department of Computer Science
   Google Scholar
• Meijer , H. and Akl , S. G. 1980 . The design and analysis of a new hybrid sorting algorithm . Information Processing Letters , 10 : 213 – 218 .
   Web of Science ®Google Scholar
• Ohya , T. , Iri , M. and Murota , K. 1984 . Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms . Journal of the Operations Research Society of Japan , 27 : 306 – 337 .
   Google Scholar
• Overmars M. H. Computational geometry on a grid—an overview Report RUU-CS-87-4 Department of Computer Science, University of Utrecht Utrecht, , Netherlands 1987
   Google Scholar
• Papadimitriou , C. H. and Bentley , J. L. . Proc. 7th Colloquium on Automata, Languages and Programming . A worst-case analysis of nearest neighbor searching by projection . pp. 470 – 482 . Berlin : Springer-Verlag . Lecture Notes in Computer Science 85, FRG
   Google Scholar
• Preparata , F. P. and Shamos , M. I. 1985 . Computational Geometry , New York, NY : Springer-Verlag .
   Google Scholar
• Rabin , M. O. 1976 . “ Probabilistic algorithms ” . In Algorithms and Complexity: New Directions and Recent Results , Edited by: Traub , J. F. 21 – 39 . New York, NY : Academic Press .
   Google Scholar
• Shamos , M. I. and Hoey , D. 1975 . Proc. IEEE 16th Annual Symposium on Foundations of Computer Science . Closest-point problems . 1975 , Berkeley, CA. pp. 151 – 162 .
   Google Scholar
• Tarjan , R. E. 1983 . “ Society for Industrial and Applied Mathematics ” . In Data Structures and Network Algorithms Philadelphia, PA
   Google Scholar
• Vaidya , P. 1986 . Proc. IEEE 27th Annual Symposium on Foundations of Computer Science . An algorithm for the all-nearest-neighbors problem . 1986 , Toronto, Ontario. pp. 117 – 122 .
   Google Scholar
• Van Emde Boas , P. 1977 . Preserving order in a forest in less than logarithmic time and linear space . Information Processing Letters , 6 : 80 – 82 .
   Google Scholar
• Van Emde Boas , P. , Kaas , R. and Zijlstra , E. 1977 . Design and implementation of an efficient priority queue . Mathematical Systems Theory , 10 : 99 – 127 .
   Google Scholar
• Yuval , G. 1976 . Finding nearest neighbours . Information Processing Letters , 5 : 63 – 65 .
   Google Scholar