Low Crossing Number Spanning Trees

 In this post, we prove that for any set $P$ of $n$ points in the plane, there is a spanning tree for $P$ such that any line in the plane intersects at most $O(\sqrt{n})$ edges of the spanning tree. This result was first proved by Welzl [W'88] and later generalized by Chazelle and Welzl [CW'89]. Such low crossing number spanning trees has many applications in computational geometry, e.g., for simplex range searching problems. We will see how to prove this result in the plane. The proof of this post is from Welzl [W'05].

We start with several definitions. Let $S$ be a set of points in the plane. 

Definition 1 (Spanning Trees). A spanning tree of $S$ is a directed acyclic graph $T=(S,E)$ where $E$ is a collection of edges with endpoints in $S$. 

Definition 2 (Crossing numbers). Given a line $l$ in the plane, the crossing number of $l$ in $T$ is defined to be the number of edges in $E$ intersecting $l$.  The crossing number of a spanning tree $T$ is defined to be the maximum crossing number of any line in the plane.

Definition 3 (Weighted Lines). A line in the plane is said to be weighted if it is associated with a weight. In this post, we will assume that all the weights are real-valued.

Definition 4 (Pseudodistance between two points). Given two points $p,q$ in the plane, and let $G$ be a collection of weighted lines in the plane. We define the pseudodistance between $p,q$ in $G$, denoted by ${\delta }_G(p,q)$, to be the sum of weights of lines in $G$ intersecting line segment $\overline{pq}$.

We prove the following theorem.

Theorem 1 [W'88]. Every set $S$ of $n$ points in the plane has a spanning tree with crossing number $O(\sqrt{n})$.

To prove the theorem, we use the following lemma.

Lemma 1. Let $G$ be a collection of weighted lines in the plane. Let $W$ be the total weight of all lines in $G$. Let $S$ be a set of $n$ points in the plane. There exist two points $p,q\in S$ such that ${\delta }_G(p,q)\le \frac{2W}{\sqrt{n}}$.

Proof of Theorem 1. We show how to construct a low crossing number spanning tree. The construction consists of $n-1$ steps. At each step, we add one edge into the tree and remove one of the points. Let $T_i$ denote the collection of all spanning tree edges we have discovered after step $i$. We use $S_i$ to denote the set of remaining points after step $i$. Initially, $T_0=\mathrm{\varnothing }$ and $S_0=S$. 

To bound the crossing number of edges, we need to consider all possible lines in the plane. The first idea is to consider a finite collection $G$ of test lines such that for any line $l^{\prime }$ in the plane, either the line is in $G$ or there is a line $l\in G$ such that the crossing numbers of $l$ and $l^{\prime }$ are the same. It is not hard to see that such a set $G$ exists and $|G|=(\genfrac{}{}{0ex}{}{n}{2})$ (the VC-dimension of a halfspace in the plane is 3).

To decide which edge to add to $T_i$ at step $i$, we first update the weights of each line in $G$. Given a line $l\in G$, we update its weight to be $(1+\mu {)}^{c_{i-1}}$ where $c_{i-1}$ is the number of edges it crosses in $T_{i-1}$ and $\mu$ is a parameter we will set later. After updating the weights, we find a pair of points $p_i,q_i\in S_{i-1}$ such that ${\delta }_G(p_i,q_i)\le \frac{2W_{i-1}}{\sqrt{n-(i-1)}}$, where $W_{i-1}$ is the total weights after updating. By Lemma 1, such a pair exists. Then we add $\overline{p_i{q}_i}$ to $T_i$ and remove $p_i$ from $S_{i-1}$ to get $S_i$. It is not hard to show that after $n-1$ iterations, we get a spanning tree. We now analyze the crossing number.

The key to the analysis is to bound the total weight $W_i$ after step $i$. Observe that to update $W_{i-1}$, we increase the weights of at most $\frac{2W_{i-1}}{\sqrt{n-i-1}}$  lines in $G$ by a factor of $1+\mu$, so

$$\begin{array}{rl}{W}_i& \le \frac{2W_{i-1}}{W_{i-1}\sqrt{n-(i-1)}}\cdot W_{i-1}\cdot (1+\mu )+(1-\frac{2W_{i-1}}{W_{i-1}\sqrt{n-(i-1)}})W_{i-1}\\ & =W_{i-1}(1+\frac{2\mu }{\sqrt{n-(i-1)}})\le |G|\prod _{j=0}^{i-1}(1+\frac{2\mu }{n-j}).\end{array}$$

After $n-1$ steps, the total weight becomes

$$\begin{array}{rl}{W}_{n-1}& \le |G|\prod _{j=0}^{n-2}(1+\frac{2\mu }{n-j})=|G|\prod _{j=2}^n(1+\frac{2\mu }{j})\\ & <|G|\exp \left(\sum _{j=1}^n\frac{2\mu }{\sqrt{j}}\right)\le \exp (4\mu \sqrt{n}+2\ln n),\end{array}$$

where the last inequality follows from $|G|\le n^2$.

On the other hand, by definition,

$$W_{n-1}=\sum _{l\in G}(1+\mu {)}^{c_l},$$

where $c_l$ is the crossing number of line $l$ in spanning tree $T_{n-1}$. Thus,

$$\sum _{l\in G}(1+\mu {)}^{c_l}\le \exp (4\mu \sqrt{n}+2\ln n).$$

We pick $\mu =\frac{\ln n}{2\sqrt{n}}$, which gives us

$$\sum _{l\in G}(1+\frac{\ln n}{2\sqrt{n}}{)}^{c_l}\le \exp (4\ln n).$$

Thus for any $l\in G$, we must have

$$\begin{array}{rl}(1+\frac{\ln n}{2\sqrt{n}}{)}^{c_l}\le \exp (4\ln n)& ⟹c_l\ln (1+\frac{\ln n}{2\sqrt{n}})\le 4\ln n\\ & ⟹c_l\frac{\ln n}{2\sqrt{n}}\le 4\ln n⟹c_l\le 8\sqrt{n},\end{array}$$

where the second last implication follows from $e^x\le (1+x)$.

Remark. The idea behind the construction is called iterative reweighting. This idea has also been used by Matoušek [M'92] to prove the partition theorem.

References:

[CW'89] Chazelle, Bernard, and Emo Welzl. "Quasi-optimal range searching in spaces of finite VC-dimension." Discrete & Computational Geometry 4 (1989): 467-489.

[M'92] Matoušek, Jiří. "Efficient partition trees." Proceedings of the seventh annual symposium on Computational geometry. 1991.

[W'88] Welzl, Emo. "Partition trees for triangle counting and other range searching problems." Proceedings of the fourth annual symposium on Computational geometry. 1988.

[W'05] Welzl, Emo. "On spanning trees with low crossing numbers." Data structures and efficient algorithms: Final Report on the DFG Special Joint Initiative (2005): 233-249