Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
share
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 ∈{1, ..., 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 (EMST) of a set V of n sites in the plane. We present an algorithm that computes EMST(V) using O(n^3 s /s^2) time and O(s) words of workspace. Our algorithm uses the fact that 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.
READ FULL TEXT