Nordic Journal of Computing Bibliography

Abstract

It is shown that a minimum spanning tree of n points in R^d under any fixed L_p-metric, with p=1,2,...,infinity can be computed in optimal O( T_d(n,n) ) time in the algebraic computational tree model. T_d(n,m) denotes the time to find a bichromatic closest pair between n red points and m blue points. The previous bound in the model was O( T_d(n,n) log n ) and it was proved only for the L₂ (Euclidean) metric. Furthermore, for d=3 it is shown that a minimum spanning tree can be found in O(n log n) time under the L₁ and L_infinity-metrics. This is optimal in the algebraic computation tree model. The previous bound was O(n log n log log n).

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: algorithms, computational geometry, networks, trees

Selected references

• S. N. Bespamyatnikh. On constructing minimum spanning trees in R^k_l. Algorithmica, 18(4):524-529, August 1997.

• Paul B. Callahan and S. Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 291-300, Austin, Texas, 25-27 January 1993.

• Kenneth L. Clarkson. Fast expected-time and approximation algorithms for geometric minimum spanning trees (extended abstract). In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 342-348, Washington, D.C., 1984.

• Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan. Scaling and related techniques for geometry problems. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 135-143, Washington, D.C., 1984.

• David Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, February 1983.

• Drago Krznaric and Christos Levcopoulos. Optimal algorithms for complete linkage clustering in d dimensions. In Igor Prívara and Peter Ruzicka, editors, Mathematical Foundations of Computer Science 1997, volume 1295 of Lecture Notes in Computer Science, pages 368-377, Bratislava, Slovakia, 25-29 August 1997. Springer.

• Michael I. Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, pages 151-162, The University of California, Berkeley, 13-15 October 1975. IEEE.

• Pravin M. Vaidya. Minimum spanning trees in k-dimensional space. SIAM Journal on Computing, 17(3):572-582, June 1988.

• Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721-736, November 1982.

Shortcuts: