New Streaming Algorithms for High Dimensional EMD and MST

Xi Chen, Rajesh Jayaram, Amit Levi +1

We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an $n$-point set $X\subset \{1,2,\dots ,\Delta {\}}^d$, and com…