<p>If I get it correctly, the result you need appears in Section 4 of <a href="http://dx.doi.org/10.1007/s00454-003-2949-y" rel="nofollow">this paper</a> (a <a href="http://www.fmf.uni-lj.si/~cabello/publications/clms-thpp-03.pdf" rel="nofollow">draft here</a>). We also needed to join pieces of different papers, as the comments here tell. </p>

CC BY-SA 3.0
2014-05-29T16:28:00.107Z
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.
John
CC BY-SA 3.0
2014-05-17T11:03:21.160Z
2014-05-17T11:03:21.160Z
someone
<p>I'm reading a paper that uses the following result:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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. </p>

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

<blockquote>
  <p>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].</p>
</blockquote>

<p>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.</p>

<p>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)? </p>

<p>Thanks.</p>

<p>References</p>

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

<p>[2] Wezl, E. On spanning trees with low crossing numbers. <em>Data Structures and Efficient Algorithms, LNCS</em> 594:233-249, 1992.</p>

CC BY-SA 3.0
2014-01-10T18:19:44.670Z
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
CC BY-SA 3.0
2014-01-10T18:47:35.710Z
Just looked up the result in Har-Peled's book. He doesn't seem to prove that the running time is $O(n^{1+\epsilon})$. Instead he has a theorem that says it is polynomial time, and then in the bibliographical notes cites Wezl's paper [2]. Har-Peled says the running time "can be improved to $O(n^{1+\epsilon})$" and then cites [2]. Caveat: I don't have the book yet (requested through ILL), but I was checking the Google books version. The statement above is in Chapter 6 section 5.
John
CC BY-SA 3.0
2014-01-10T19:30:07.107Z
That's true. and re-reading the reference [1], I think your interpretation is correct: that the only reference to the actual result is in the 'private communication'. Which means that it would be interesting to prove this from scratch.
Suresh Venkat
CC BY-SA 3.0
2014-01-10T19:39:17.740Z
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
CC BY-SA 3.0
2014-01-10T20:06:29.810Z
Yes! I think I see that. Except at the top level of the simplicial partition tree, each edge of such an arbitrary spanning tree is contained on the interior of one of the simplices, and thus the gaurantee holds. Then there are only $O(\sqrt{n})$ other edges in the spanning tree (those between points in the top level simplices of the partition tree), so I think everything should work from that. Cool. The final trick is to do it so that no edges cross (which is used in the paper I'm reading). Not a proof, but I think I get the idea, thanks!
John
CC BY-SA 3.0
2014-01-10T20:54:01.213Z
If you do work out the details, writing it up might be helpful. I find that there are a  number of sketched proofs in this area that could do with some fleshing out.
Suresh Venkat
CC BY-SA 3.0
2014-01-10T21:08:14.147Z
not sure it helps at all (been a while since I looked at this), but section 5.3. of [Chazelle's book](http://www.cs.princeton.edu/~chazelle/book.html) has information about simplicial partitions and low crossing number spanning trees
Sasho Nikolov
CC BY-SA 3.0
2014-01-13T17:18:16.053Z
Ok, I now see how to obtain a spanning tree of crossing number $O(n^{1+\epsilon})$ for any $\epsilon > 0$ using the partition trees. At each node of the partition tree, arbitrarily select a point from each of its child node's canonical subsets and connect them up as a polygonal chain. The resulting structure is a spanning tree, and the crossing number of the spanning tree uses the same recurrence as the query time, which can be made $O(n^{1/2 + \epsilon})$. I do not yet see, however, how to obtain one which is $O(n^{1/2})$.
John
CC BY-SA 3.0
2014-01-13T17:23:42.170Z
The above comment should read $O(n^{1/2 + \epsilon})$, not $O(n^{1+\epsilon})$ for the crossing number. Some combination of stack exchange and iOS is not allowing me to click on the edit button.
John
CC BY-SA 3.0
2014-01-15T21:38:36.060Z
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: http://sarielhp.org/p/09/crossing/. None of these alternative techniques yield useful algorithms, however.
Sariel Har-Peled
CC BY-SA 3.0
2014-01-16T17:25:09.353Z
Thanks. An additional follow up question: the algorithm I'm interested in not only requires a spanning tree with low crossing number, but one that is not self intersecting. I do not see this mentioned in any of these papers (yet). Is this simply assumed? I do not see a priori, why it should be the case.
John
CC BY-SA 3.0
2014-03-03T05:02:43.910Z
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
CC BY-SA 3.0
2014-04-14T14:48:18.243Z
@SarielHar-Peled, I agree that you can do that, but I can't see how to do it without hurting the time bound. The main problem I have in mind is that since there is no guarantee that a point doesn't lie in multiple simplexes, it seems that when I want to merge the spanning trees of two simplexes which overlap, their respective sub-spanning trees may be arbitrarily snarled together making finding a valid edge between the two difficult.
John
CC BY-SA 3.0
2014-04-15T20:51:57.500Z
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
<reference-request><cg.comp-geom>
Computing spanning trees with low crossing number using simplicial partitions
John
# Computing spanning trees with low crossing number using simplicial partitions

(Asked by: username_0 on 2014-01-10)

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

**Tags:** reference-request, cg.comp-geom

> **Comments:**
> **username_1**: username_3's book on geometric approximations has a direct proof for the $\sqrt{n}$ result that doesn't need simplicial partitions.  
> **username_0**: Just looked up the result in Har-Peled's book. He doesn't seem to prove that the running time is $O(n^{1+\epsilon})$. Instead he has a theorem that says it is polynomial time, and then in the bibliographical notes cites Wezl's paper [2]. Har-Peled says the running time "can be improved to $O(n^{1+\epsilon})$" and then cites [2]. Caveat: I don't have the book yet (requested through ILL), but I was checking the Google books version. The statement above is in Chapter 6 section 5.  
> **username_1**: That's true. and re-reading the reference [1], I think your interpretation is correct: that the only reference to the actual result is in the 'private communication'. Which means that it would be interesting to prove this from scratch.  
> **username_1**: 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.  
> **username_0**: Yes! I think I see that. Except at the top level of the simplicial partition tree, each edge of such an arbitrary spanning tree is contained on the interior of one of the simplices, and thus the gaurantee holds. Then there are only $O(\sqrt{n})$ other edges in the spanning tree (those between points in the top level simplices of the partition tree), so I think everything should work from that. Cool. The final trick is to do it so that no edges cross (which is used in the paper I'm reading). Not a proof, but I think I get the idea, thanks!  
> **username_1**: If you do work out the details, writing it up might be helpful. I find that there are a  number of sketched proofs in this area that could do with some fleshing out.  
> **username_2**: not sure it helps at all (been a while since I looked at this), but section 5.3. of [Chazelle's book](http://www.cs.princeton.edu/~chazelle/book.html) has information about simplicial partitions and low crossing number spanning trees  
> **username_0**: Ok, I now see how to obtain a spanning tree of crossing number $O(n^{1+\epsilon})$ for any $\epsilon > 0$ using the partition trees. At each node of the partition tree, arbitrarily select a point from each of its child node's canonical subsets and connect them up as a polygonal chain. The resulting structure is a spanning tree, and the crossing number of the spanning tree uses the same recurrence as the query time, which can be made $O(n^{1/2 + \epsilon})$. I do not yet see, however, how to obtain one which is $O(n^{1/2})$.  
> **username_0**: The above comment should read $O(n^{1/2 + \epsilon})$, not $O(n^{1+\epsilon})$ for the crossing number. Some combination of stack exchange and iOS is not allowing me to click on the edit button.  
> **username_3**: 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: http://sarielhp.org/p/09/crossing/. None of these alternative techniques yield useful algorithms, however.  
> **username_0**: Thanks. An additional follow up question: the algorithm I'm interested in not only requires a spanning tree with low crossing number, but one that is not self intersecting. I do not see this mentioned in any of these papers (yet). Is this simply assumed? I do not see a priori, why it should be the case.  
> **username_3**: 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...  
> **username_0**: @SarielHar-Peled, I agree that you can do that, but I can't see how to do it without hurting the time bound. The main problem I have in mind is that since there is no guarantee that a point doesn't lie in multiple simplexes, it seems that when I want to merge the spanning trees of two simplexes which overlap, their respective sub-spanning trees may be arbitrarily snarled together making finding a valid edge between the two difficult.  
> **username_3**: 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...  

---

## 1 answers

### Answer by username_4 on 2014-05-17. Score: 2 | Accepted answer

If I get it correctly, the result you need appears in Section 4 of [this paper](http://dx.doi.org/10.1007/s00454-003-2949-y) (a [draft here](http://www.fmf.uni-lj.si/~cabello/publications/clms-thpp-03.pdf)). We also needed to join pieces of different papers, as the comments here tell.

> **Comments:**
> **username_0**: 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.  

---

