# Streaming Euclidean MST to a Constant Factor

arXiv: https://arxiv.org/abs/2212.06546 · HTML: https://mlsanity.com/paper/2212.06546/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2022.

## Built on by (most cited first, 1 of 1)

- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)

## Abstract (arXiv)

We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an n-point set X subset ℝd. In the streaming model, the points in X can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, (1+ε) approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG '05]. However, for high dimensional spaces the best known approximation for this problem was tildeO(log n), due to [Chen, Jayaram, Levi, Waingarten, STOC '22], improving on the prior O(log2 n) bound due to [Indyk, STOC '04] and [Andoni, Indyk, Krauthgamer, SODA '08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any ε≥ 1, our algorithm achieves an tildeO(ε-2) approximation in nO(ε) space. We complement this by proving that any single pass algorithm which obtains a better than 1.10-approximation must use Omega(√n) space, demonstrating that (1+ε) approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that (1+ε) approximations are possible in sublinear space with O(1/ε) passes over the stream. More generally, for any α ≥ 2, we give a α-pass streaming algorithm which achieves a (1+O(fraclog α + 1 α ε)) approximation in nO(ε) dO(1) space. Our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first (1+ε)-approximation to Euclidean MST in a constant number of rounds in the MPC model.