## March 2, 2018:

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

## Jordan Jorgensen

In the limited-workspace model, we assume that the input of size $n$
lies in a random access read-only memory. The output has to be reported
sequentially, and it cannot be accessed or modified. In addition, there
is a read-write workspace of $O(s)$ words, where $s\in\{1,\dots,n\}$ is
a given parameter. In a time-space trade-off, we are interested in how
the running time of an algorithm improves as $s$ varies from $1$ to $n$.
We present a time-space trade-off for computing the Euclidean minimum
spanning tree ($\mathrm{EMST}$) of a set $V$ of $n$ sites in the
plane. We present an algorithm that computes $\mathrm{EMST}(V)$ using
$O\bigl(n^3\tfrac{\log s}{s^2}\bigr)$ time and $O(s)$ words of
workspace. Our algorithm uses the fact that $\mathrm{EMST}(V)$ is a
subgraph of the bounded-degree relative neighborhood graph of $V$, and
applies Kruskal's MST algorithm on it. To achieve this with limited
workspace, we introduce a compact representation of planar graphs,
called an $s$-net which allows us to manipulate its component structure
during the execution of the algorithm.

(Based on a paper by Bahareh Banyassady, Luis Barba, and Wolfgang Mulzer from LATIN 2018.)