Sublinear-time approximation of Euclidean minimum spanning tree

ABSTRACT

We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in ℝ^d. We focus on the situation when the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within 1 + ε using only Õ(√ poly(1/ε)) queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbors queries.

REFERENCES

• 1: Pankaj K. Agarwal, Range searching, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 2: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991
• 3: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, pp. 1--56. AMS Press, 1999.
• 4: Sunil Arya , Gautam Das , David M. Mount , Jeffrey S. Salowe , Michiel Smid, Euclidean spanners: short, thin, and lanky, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.489-498, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225191]
• 5: Sunil Arya , David M. Mount , Michiel Smid, Dynamic algorithms for geometric spanners of small diameter: randomized solutions, Computational Geometry: Theory and Applications, v.13 n.2, p.91-107, June 1999 [doi>10.1016/S0925-7721(99)00014-0 ]
• 6: S. Arya and M. Smid. Efficient construction of a bounded-degree spanner with low weight. Algorithmica, 17(1):33--54, January 1997.
• 7: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 8: Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
• 9: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 10: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 11: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 12: Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
• 13: Bernard Chazelle , Ronitt Rubinfeld , Luca Trevisan, Approximating the Minimum Spanning Tree Weight in Sublinear Time, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.190-200, July 08-12, 2001
• 14: Artur Czumaj , Christian Sohler, Property Testing with Geometric Queries, Proceedings of the 9th Annual European Symposium on Algorithms, p.266-277, August 28-31, 2001
• 15: D. Eppstein. Spanning trees and spanners. In Handbook of Computational Geometry, pp. 425--461. Elsevier Science B.V., 1997.
• 16: D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete & Computational Geometry, 13(1):111--122, Jan 1995
• 17: J. Erickson. On the relative complexity of some geometric problems. In Proceedings of the 7th Canadian Conference on Computational Geometry, pp. 85--90, 1995.
• 18: R. A. Finkel and J. L. Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4:1--9, 1974.
• 19: Matthias Fischer , Friedhelm Meyer auf der Heide , Willy-Bernhard Strothmann, Dynamic Data Structures for Realtime Management of Large Geormetric Scences (Extended Abstract), Proceedings of the 5th Annual European Symposium on Algorithms, p.157-170, September 15-17, 1997
• 20: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 21: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan, Fast Greedy Algorithms for Constructing Sparse Geometric Spanners, SIAM Journal on Computing, v.31 n.5, p.1479-1500, 2002 [doi>10.1137/S0097539700382947]
• 22: G. S. Lueker. A data structure for orthogonal range queries. In Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pp. 28--34, 1978.
• 23: Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142732]
• 24: Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001 [doi>10.1145/500559.500562]
• 25: J. Ruppert and R. Seidel. Approximating the d-dimensional complete Euclidean graph. In Proceedings of the 3rd Canadian Conference on Computational Geometry, pp. 207--210, 1991.
• 26: J. S. Salowe. Constructing multidimensional spanner graphs. International Journal of Computational Geometry and Applications, 1(2):99--107, 1991.
• 27: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 28: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 29: M. I. Shamos and D. Hoey. Closest-point problems. In Proceedings of the 16th IEEE Symposium on Foundations of Computer Science, pp. 151--162, 1975.
• 30: Pravin M. Vaidya, Minimum spanning trees in k-dimensional space, SIAM Journal on Computing, v.17 n.3, p.572-582, June 1988 [doi>10.1137/0217035]
• 31: D. E. Willard. Predicate-Oriented Database Search Algorithms. PhD thesis, Harvard University, Aiken Computation Lab, Cambridge, MA, 1978. Report TR-20--78.
• 32: A.C.-C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721--736, November 1982.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory