Before revision:  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).
After revision:  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) 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).