Euclidean minimum spanning trees and bichromatic closest pairs

ABSTRACT

We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in @@@@d in time &Ogr;(&Tgr;d(N, N) logd N), where &Tgr;d(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in @@@@d. If &Tgr;d(N, N) = &OHgr;(N1+&egr;), for some fixed &egr; > 0, then the running time improves to &Ogr;(&Tgr;d(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time &Ogr;((nm log n log m)2/3 + m log2 n + n log2 m) in @@@@3, which yields an &Ogr;(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in @@@@3.

REFERENCES

• Cl: Kenneth L. Clarkson, Fast expected-time and approximation algorithms for geometric minimum spanning trees, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.342-348, December 1984 [doi>10.1145/800057.808699]
• 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]
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 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]
• ESh: H. Edelsbrunner and M. Sharir, A hyperplane incidence problem with applications to counting distances, manuscript, 1990.
• GBT: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• PT: Franco P. Preparata , Roberto Tamassia, Efficient Spatial Point Location (Extended Abstract), Proceedings of the Workshop on Algorithms and Data Structures, p.3-11, August 17-19, 1989
• ST: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• Se: Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
• Se2: Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
• SH: M. Shamos and D. Hoey, Closest-point problems, Proceedings 16th Annual IEEE Symposium on Foundations of Computer Science, 1975, pp. 151-162.
• Va: P. Vaidya, A fast approximate algorithm for minimum spanning tree in k-dimensional space, Proceedings 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, pp. 403-407.
• Ya: A. Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Computing 11 (1982), 721-736.

INDEX TERMS

Primary 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

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms