variations on the geometric MST, see Eppstein's survey paper
\cite{eppstein:spanning}.
+There are also plentiful interesting results on expected properties of the
+Euclidean MST of various random point configurations. These are well covered
+by the monographs of Steele \cite{steele:ptco} and Yukich \cite{yukich:pteucl}.
+
\paran{Steiner trees}
The constraint that the segments in the previous example are allowed to touch
each other only in the given points looks artificial and it is indeed uncommon in
$\widetilde\O(f) = \O(f\cdot\log^{\O(1)} f)$ and $\poly(n)=n^{\O(1)}$.}
queries to a~data structure containing the points. The data structure is expected
to answer orthogonal range queries and cone approximate nearest neighbor queries.
-There is also a~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation
+There is also an~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation
algorithm for the MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}.
(This is still sub-linear since the corresponding graph has roughly $n^2$ edges.)