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

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

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

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

CC BY-SA 3.0
2013-05-15T17:46:39.250Z
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
CC BY-SA 3.0
2013-05-15T20:29:27.730Z
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
CC BY-SA 3.0
2013-05-16T12:31:30.740Z
@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
CC BY-SA 3.0
2013-05-16T18:50:15.373Z
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
CC BY-SA 3.0
2013-05-15T17:27:23.993Z
2013-05-15T17:27:23.993Z
Michiel Smid
<p>I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:</p>

<blockquote>
  <p>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)<br>
  <strong>The gap property:</strong> 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| &gt; w \cdot min(|pq|, |rs|)$</p>
</blockquote>

<p>Then (at the same page) comes the following Theorem:</p>

<blockquote>
  <p>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$.<br>
  1. If $w \geq 0$, then each points of $S$ is the source of at most one edge if $E$.<br>
  2. if $w&gt;0$, then $wt(E)&lt;(1+2/w) \cdot wt(MST(S))\log n$ (where $MST(S)$ denotes a minimum spanning tree of $S$.<br>
  3. [not relevant for the question]</p>
</blockquote>

<hr>

<h1>Background and context</h1>

<p>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')&lt;(1+2/w) \cdot wt(MST(S))$.<br>
Then comes an induction on $m$ in which the claim  $wt(E)&lt;(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  </p>

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

<h1>My question</h1>

<p>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)&lt;(1+2/w) \cdot wt(MST(S))$". The same proof would get a better bound (without the $\log m$)</p>

<graph-theory><cg.comp-geom>
Understanding the "gap theorem" in geometric spanners
Ramzi Kahil
# Understanding the "gap theorem" in geometric spanners

(Asked by: username_0 on 2013-05-13)

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

**Tags:** graph-theory, cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2013-05-15. Score: 3 | Accepted 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$.

> **Comments:**
> **username_0**: 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$?  
> **username_2**: 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.  
> **username_0**: @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)?  
> **username_2**: 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.  

---

