Computing spanning trees with low crossing number using simplicial partitions I'm reading a paper that uses the following result:


  Let $S$ be a set of $n$ points in the plane. Then a spanning tree for $S$ with crossing number $O(\sqrt{n})$ can be computed in $O(n^{1+\epsilon})$ time for any $\epsilon &gt; 0$.


The paper refers the reader to Matoušek's paper [1] for this result. However, Matoušek does not discuss spanning trees of points in [1], rather several methods for computing simplicial partition trees. 

So I've been trying to track down where the result comes from. I finally found, in [2], the following statement: 


  So-called simplicial partitions ([Mat91b], see Section 5) can be used to obtain a spanning tree with crossing number $O(\sqrt{n})$ in time $O(n^{1+\epsilon})$ for any $\epsilon &gt; 0$ (where the constant in the crossing numbers depends on $\epsilon$), [Mat91a].


The reference [Mat91b] in the quote is my reference [1], and the reference [Mat91a] is a private communication between Wezl and Matoušek. It seems that this sentence from [2] is most likely why [1] is referenced in the paper I'm currently reading. I think this is a slight mistake, since [Mat91b] appears to be included as a reference for simplicial partitions, and [Mat91a] (the private communication) is the reference for the entire section and hence the claim. I must admit the first time I read this sentence I made the same mistake, but after searching in vain for the result in [1], have come to the conclusion above.

So my question is this: has the proof of this result appeared in the literature? Perhaps it is obvious (it is not yet obvious to me, but I am still learning about these algorithms). If it is not obvious, I am hoping someone can either provide me with a reference to where it has appeared, or a (rough?) explanation of how a simplicial partition of a point set can be used to construct a spanning tree of the point set with stabbing number $O(\sqrt{n})$ in $O(n^{1 + \epsilon})$ time (or any other $O(n^{1+\epsilon})$ time method, really)? 

Thanks.

References

[1] Matoušek, J. Efficient Partition Trees. Discrete Comput. Geom., 8:315-334, 1992.

[2] Wezl, E. On spanning trees with low crossing numbers. Data Structures and Efficient Algorithms, LNCS 594:233-249, 1992.
If I get it correctly, the result you need appears in Section 4 of this paper (a draft here). We also needed to join pieces of different papers, as the comments here tell.