X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=appl.tex;h=f9d59ab811f3b882a21ea55de4c806c207036047;hb=124f193d14bed24539c5cd59407637cc38dbe740;hp=b9b9b2d4a8885b2b84096eefeb3a474fd24f1895;hpb=cecb911d6e00af99547101918045b6ff05276692;p=saga.git

diff --git a/appl.tex b/appl.tex
index b9b9b2d..f9d59ab 100644
--- a/appl.tex
+++ b/appl.tex
@@ -103,6 +103,10 @@ based on the sweep-line technique and the Red rule. For other
 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
@@ -141,7 +145,7 @@ produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\s
 $\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.)