# 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  for this result. However, Matoušek does not discuss spanning trees of points in , 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 , 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 , and the reference [Mat91a] is a private communication between Wezl and Matoušek. It seems that this sentence from  is most likely why  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 , 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

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

 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. Jan 10, 2014 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. Jan 10, 2014 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. Jan 15, 2014 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... Mar 3, 2014 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... Apr 15, 2014 at 20:51