Understanding the "gap theorem" in geometric spanners

Question

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$)

Answer 1

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