The average performance analysis of a closest‐pair algorithm

References

• Bentley , J. L. 1980 . Multidimensional divide‐and‐conquer . Communications of Association for Computing Machinery , 23 ( 2 ) : 214 – 229 .
   Web of Science ®Google Scholar
• Bentley , J. L. and Shamos , M. I. 1976 . Divide‐and‐conquer in multidimensional space . Proceedings, ACM Symp. Theory of Computing , 16 ( 2 ) : 220 – 230 .
   Google Scholar
• Bentley , J. L. and Shamos , M. I. 1978 . Divide‐and‐conquer for linear expected time . Information Processing Letters , 7 ( 2 ) : 87 – 91 .
   Web of Science ®Google Scholar
• Bentley , J. L. , Weide , B. W. and Yao , A. C. C. 1980 . Optimal expected time analysis for closest point problem . TransactionsonMathematicalSoftware , 6 ( 4 ) : 563 – 580 .
   Google Scholar
• Blum , M. , Floyd , R. W. , Pratt , V. R. , Rivest , R. L. and Tarjan , R. E. 1972 . Time bound for selection . Journal of Computer and System Sciences , 7 ( 2 ) : 724 – 742 .
   Google Scholar
• Fortune , S. and Hopcroft , J. E. 1979 . A note on Rabin's nearest‐neighbor algorithm . Information Processing Letters , 8 ( 1 ) : 20 – 23 .
   Web of Science ®Google Scholar
• Goldman , J. R. 1967 . Stochastic point process: limit theorems . Ann. Math. Statist , 38 ( 2 ) : 771 – 779 .
   Google Scholar
• Marks , E. S. 1948 . A lower bound for the expected travel among m random points . Ann. Math. Statist , 19 ( 2 ) : 419 – 422 .
   Google Scholar
• Miles , R. E. 1970 . On the homogeneous planar Poisson point process . Mathematical Biosciences , 6 ( 2 ) : 85 – 127 .
   Google Scholar
• Rabin , M. O. “ Probabilistic algorithms ” . In In Algorithms and Complexity: New Direction and Recent Results Edited by: Traub , J. F .
   Google Scholar
• Shamos , M. I. 1978 . Computational Geometry , Vol. 16 , Yale Univ . Ph.D. dissertation
   Google Scholar
• Shamos , M. I. and Hoey , D. 1975 . Closest point problems . Proceedings, 16th Annual IEEE Symp , 16 ( 2 ) : 151 – 162 . on Foundations of Computer Sciences
   Google Scholar
• Tamminen , M. 1982 . The extensible cell method for closest point problems . BIT , 22 ( 1 ) : 27 – 41 .
   Web of Science ®Google Scholar
• Weide , B. W. Statistical Methods in Algorithm Design and Analysis Ph.D.dissertation
   Google Scholar
• Yuval , G. 1975 . Finding nearest neighbours in K dimensions . Information Processing Letters , 3 ( 2 ) : 113 – 114 .
   Google Scholar
• Yuval , G. 1976 . Finding nearest neighbours . Information Processing Letters , 5 ( 3 ) : 63 – 65 .
   Google Scholar