3
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • $\begingroup$ Sariel Har-Peled's book on geometric approximations has a direct proof for the $\sqrt{n}$ result that doesn't need simplicial partitions. $\endgroup$
    – Suresh Venkat
    Jan 10, 2014 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Jan 10, 2014 at 19:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sariel Har-Peled
    Jan 15, 2014 at 21:38
  • 1
    $\begingroup$ 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... $\endgroup$
    – Sariel Har-Peled
    Mar 3, 2014 at 5:02
  • 1
    $\begingroup$ 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... $\endgroup$
    – Sariel Har-Peled
    Apr 15, 2014 at 20:51

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very cool, thanks. I had just been thinking about the problem this morning again, and had realized that a tree with Steiner points could be computed from a self-intersecting tree, though I didn't realize it could be done in that time bound (I had a much slower algorithm in mind) nor that you could then compute a non-steiner point version only doubling the crossing number. This really made my morning. Now I can go get some coffee =D. $\endgroup$
    – John
    May 29, 2014 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.