# 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 > 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 > 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.

• Sariel Har-Peled's book on geometric approximations has a direct proof for the $\sqrt{n}$ result that doesn't need simplicial partitions. – Suresh Venkat Jan 10 '14 at 18:19
• while this is not an answer, I think the way to go is to compute the simplicial partition, compute a spanning tree in each partition recursively, and then "glue" the trees up essentially arbitrarily. the low crossing number of the partition structure yields the desired bound. – Suresh Venkat Jan 10 '14 at 19:39
• Yes. To get the improved running time you essentially either has to use partition trees, or replicate some parts of their construction. In short, it is a horrendous mess. For me, the existence of such trees and that they are polynomial time computable is the interesting tidbit. BTW, I have a writeup showing the existence of such trees using LP duality, and Matousek and Sharir has a writeup showing the existence of such trees using algebraic techniques. For my writeup, see here: sarielhp.org/p/09/crossing. None of these alternative techniques yield useful algorithms, however. – Sariel Har-Peled Jan 15 '14 at 21:38
• You can gaurentee non-intersecting by locally resolving such intersections until they are completely removed. It is easy to argue this only improves the tree you have at hand... – Sariel Har-Peled Mar 3 '14 at 5:02
• Timothy Chan has a recent paper doing partition trees that have cells that do not overlap. It is even messier... ;). One can argue that after $O(n^c)$ flips you would be done, but $c$ is not tiny... – Sariel Har-Peled Apr 15 '14 at 20:51