Corrected bugs reported by Koubek.

[saga.git] / appl.tex

diff --git a/appl.tex b/appl.tex
index b9b9b2d4a8885b2b84096eefeb3a474fd24f1895..f9d59ab811f3b882a21ea55de4c806c207036047 100644 (file)
--- 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.)