Selecting distances in the plane

ABSTRACT

We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo [Me1]. The expected running time of our algorithm is &Ogr;(n4/3 log 8/3 n). A deterministic version of our procedure runs in time &Ogr;(n3/2 log5/2 n). Both versions improve the previously best known upper bound of &Ogr;(n9/5 log4/5 n) by Chazelle [Ch]. A simple &Ogr;(n log n) time algorithm for computing an approximation of the median distance is also presented.

REFERENCES

• BO: J.L. Bentley and T. Ottmann, Algorithms for reporting and counting geometric intersections~ IEEE Trans. on Computers C-28 (1979), 643- 647.
• BFPRT: M. Blum, R.W. Floyd, V. Pratt, R.L. Rivest, and R.E. Tarjan, Time bounds for selection, J. Computer and Systems Sciences 7 (1973), 448- 461.
• Ch: Bernard Chazelle, New techniques for computing order statistics in Euclidean space (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.125-134, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323251]
• CL: B. M. Chazelle , D. T. Lee, On a circle placement problem, Computing, v.36 n.1-2, p.1-16, 1986 [doi>10.1007/BF02238188]
• CEGSW: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• CS: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• Co: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• CV: Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGPPSS: Herbert Edelsbrunner , Leonidas J. Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.214-229, July 11-15, 1988
• EGS: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• FL: Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
• HS: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• Ma: Jiří Matoušek, Cutting hyperplane arrangements, Proceedings of the sixth annual symposium on Computational geometry, p.1-9, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98528]
• Me1: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• Me2: N. Megiddo, Partition with two lines in the plane, J. Algorithms 6 (1985), 430-433.
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Sa: J. C. Salowe, Selection problems in computational geometry, Rutgers University, New Brunswick, NJ, 1987
• SPP: A. Sch6nhage, M. Paterson, and N. Pipinger, Finding the median, J. Computer and Systems Sciences 13 (1976), 184-199.
• SV: Y. Shiloach and U. Vishkin, Finding the maximum, merging and sorting in a parallel computation model, 3'. Algorithms 2 (1981), 88-102.
• TVs: R. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm, SIAM J. Computing 14, (~085), 8~2-874.
• TVt: Roberto Tamassia , Jeffrey S Vitter, Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures, Brown University, Providence, RI, 1989
• Va: L. Valiant, Parallelism in comparison problems, SIAM J. Computing 4 (1975), 348-345.
• Vi: U. Vishldn, Synchronous parallel computation--- a survey, Dept. Comp. Sci. Tech. l:tept. 71, Flew York University, New York, 1983.
• Ya: A. Yao, On constructing minimum spanning tree in k-dimensional space and related problems, SIAM J. Computing 11 (1982), 721-736.3

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms