On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
SIAM Journal on Computing1982Vol. 11(4), pp. 721–736
Citations Over TimeTop 10% of 1982 papers
Abstract
The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics: Euclidean, rectilinear, and $L_\infty $. By employing a subroutine that solves the post office problem, we show that, for fixed $k \geqq 3$, such a minimum spanning tree can be found in time $O(n^{2 - a(k)} (\log n)^{1 - a(k)} )$, where $a(k) = 2^{ - (k + 1)} $, The bound can be improved to $O((n\log n)^{1.8} )$ for points in 3-dimensional Euclidean space. We also obtain $o(n^2 )$ algorithms for finding a farthest pair in a set of n points and for other related problems.
Related Papers
- → Minimum Diameter Spanning Trees and Related Problems(1991)86 cited
- → Geometric Minimum Diameter Minimum Cost Spanning Tree Problem(2009)5 cited
- → The Minimum Moving Spanning Tree Problem(2021)1 cited
- → Approximate Minimum Spanning Tree for Points Moving in a Euclidean Two-Dimensions Plane(2013)1 cited