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 random-access memory that can only be read. The edges of the Euclidean minimum spanning tree $text{EMST}(S)$ have to be reported sequentially, and they cannot be accessed or modified afterwards. There is a parameter $s in {1, dots, n}$ so that the algorithm may use $O(s)$ cells of read-write memory (called the workspace) for its computations. Our goal is to find an algorithm that has the best possible running time for any given $s$ between $1$ and $n$. We show how to compute $text{EMST}(S)$ in $Obig((n^3/s^2)log s big)$ time with $O(s)$ cells of workspace, giving a smooth trade-off between the two best known bounds $O(n^3)$ for $s = 1$ and $O(n log n)$ for $s = n$. For this, we run Kruskals algorithm on the relative neighborhood graph (RNG) of $S$. It is a classic fact that the minimum spanning tree of $text{RNG}(S)$ is exactly $text{EMST}(S)$. To implement Kruskals algorithm with $O(s)$ cells of workspace, we define $s$-nets, a compact representation of planar graphs. This allows us to efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted.
Download