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 (EMST) of a set V of n sites in the plane. We present an algorithm that computes EMST(V) using O(S) in O}\big( (n^3 \log s /s^2) time and\big)  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(S) is exactly \text{EMST}(S). To implement } 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 .
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 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}\big( (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 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 .
R
In the limited-workspace model
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
R
the input of size n lies in a random access read-only memory . The output has
S resides in a random-access memory that can only be read. The edges of the Euclidean minimum spanning tree \text{EMST
R
it
they
R
. In addition, there is a read-write workspace of O(s ) words, where s
afterwards. There is a parameter s
R
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
so that the algorithm may use O(s) cells of read-write memory (called the workspace) for its computations. Our goal is to find
R
computes EMST(V) using O
has the best possible running time for any given s between 1 and n. We show how to compute \text{EMST
D
\log s
R
time and
\log s
A
time with
R
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
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
R
MST algorithm on it. To achieve this with limited
algorithm with O(s) cells of
R
introduce
define s-nets,
R
, called an s-net which
. This
R
manipulate its component structure during the execution of the algorithm
efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted