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

  • $\begingroup$ 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$? $\endgroup$ Commented May 15, 2013 at 17:46
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 15, 2013 at 20:29
  • $\begingroup$ @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)? $\endgroup$ Commented May 16, 2013 at 12:31
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 16, 2013 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.