Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees

Bahareh Banyassady, Luis Barba, Wolfgang Mulzer

We present time-space trade-offs for computing the Euclidean minimum spanning tree of a set $S$ of $n$ point-sites in the plane. More precisely, we assume that $S$ resides in a ran…