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

Abstract

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 $O((n^3/s^2)\log s)$ 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 Kruskal's 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 Kruskal's 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.

19 pages, 23 figures; a preliminary version appeared in LATIN 2018

References in corpus (3)

• A Time-Space Trade-off for Computing the k-Visibility Region of a Point in a Polygon
• Geometric Algorithms with Limited Workspace: A Survey
• Time-Space Trade-offs for Triangulations and Voronoi Diagrams