# Understanding the “gap theorem” in geometric spanners

I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:

Intuitively: A set of directed edges satisfies the gap property, if the sources of any two distinct edges are "far" apart (relative to the shorter of the two edges)
The gap property: Let $w \geq 0$ be a real number, and let $E$ be a set of directed edges in $\mathbb{R}^{d}$. We way that $E$ satisfies the $w-gap\ property$ if for any two distinct edges $(p,q)$ and $(r, s)$ in $E$, we have : $|pr| > w \cdot min(|pq|, |rs|)$

Then (at the same page) comes the following Theorem:

Let $S$ be a set of $n$ points in $\mathbb{R}^{d}$, and let $E \in S \times S$ be a set of directed edges that satisfies the $w-gap\ property$.
1. If $w \geq 0$, then each points of $S$ is the source of at most one edge if $E$.
2. if $w>0$, then $wt(E)<(1+2/w) \cdot wt(MST(S))\log n$ (where $MST(S)$ denotes a minimum spanning tree of $S$.
3. [not relevant for the question]

# Background and context

In the proof of the second claim, there is inner claim that there exists a set $E' \subseteq E$ that is of size $m/2$ such that $wt(E')<(1+2/w) \cdot wt(MST(S))$.
Then comes an induction on $m$ in which the claim $wt(E)<(1+2/w) \cdot wt(MST(S))\log m$ for any set $E$ that has less that $m$ edges. (Note: $n$ can be replaced by $m$ because $m \leq n$ in every graph that satisfies the $w-gap\ property$). The main point of the induction is relaying on the existence of an subset $E'$ of $E$ which has at least $m/2$ edges, and weight $(1+2/w) \cdot wt(MST(S))$. Then any set $E$ can be partitioned into 2 sets

• $E'$ of weight $<(1+2/w) \cdot wt(MST(S))$. (whose existence was proofed before)
• $E \setminus E'$ of weight $<(1+2/w) \cdot wt(MST(S)) \cdot \log m$. (according to the induction claim)

# My question

Why is there the $\log m$? It seems to me that if the induction claim was "For every $E$ with less that $m$ edges $wt(E)<(1+2/w) \cdot wt(MST(S))$". The same proof would get a better bound (without the $\log m$)

## 1 Answer

Let's write $C = (1+2/w) wt(MST(S))$. The set $E$ satisfies the $w$-gap property and has $m$ edges. It can be partitioned into 2 sets:

One set is $E'$, which is a special subset of $E$. It is chosen such that we can easily prove that its weight is at most $C$.

The other set $E''$ (which is $E \setminus E'$) has $m/2$ edges; we only know that it satisfies the $w$-gap property. By the induction hypothesis, the weight of $E''$ is at most $C \log(m/2)$.

From this, it follows that the set $E$ has weight at most $C + C \log(m/2) = C \log m$.

• I think you didn't understand my question. I asked, why the induction hypothesis cannot be reduced to $C$? Why has to be there the $\log m$? – Ramzi Kahil May 15 '13 at 17:46
• You can't just reduce the induction hypothesis to C, because then you're concluding that the new set has size 2C, which breaks the induction. – Suresh Venkat May 15 '13 at 20:29
• @SureshVenkat Thanks, you are right about the 2C, but I still don't understand where the log m comes from. Why can't I replace it with a 2 for instance? Why is it not something bigger (say m)? – Ramzi Kahil May 16 '13 at 12:31
• Try it and see what happens. you replace the log m by a 2, then the inductive hypothesis will give you 2C + 2C = 4C. Replace it by a 4, and you'll get 8, and so on. This is standard recurrence analysis. – Suresh Venkat May 16 '13 at 18:50