A lemma regarding cones covering $\mathbb{R}^d$

Added: Pointers to some references with the same conclusion as the wolloing lemma may be helpful to understand it, and are appreciated.

In A Probabilistic Theory of Pattern Recognition By Luc Devroye, László Györfi, Gábor Lugosi, there is a lemma, which is purely geometrical and combinatorial. Following is a rephrased version by me. (To see the original text, just click the link. I am not sure if my rephrasing is correct based on my understanding, but I try to rephrase it in a more clear way.)

Notations:

• For $x\in \mathbb{R}^d$ and $\theta \in (0, \pi/2)$, the set $C(x, \theta) := \{y \in \mathbb{R}^d: |angle(\bar{0x},\bar{0y})| \leq \theta \}$ is a cone with vertex at $0 \in \mathbb{R}^d$.
• Denote the closed ball centered at $x\in \mathbb{R}^d$ with radius $r$ as $S_{x,r}$.

Lemma 5.5 Let $θ ∈ (0, π/2)$ be fixed. Then there exists a set $\{x_1 , . . . , x_{\gamma_d} \} ⊂ \mathbb{R}^d$ such that $$\mathbb{R}^d = \cup_{i=1}^{\gamma_d} C(x_i, \theta).$$ Furthermore, it is always possible to take $$\gamma_d \leq (1+\frac{1}{\sin(\theta/2)})^d-1.$$ Proof: WLOG, assume $\|x_i\|=1$ for all $i$. Define $r:=2\sin(\theta/2)$. Then $$\{x: \|x\|=1\} \cap S_{x_i, r} = \{ x: \|x\|=1\} \cap C(x_i, \theta).$$ Consider the case where $\|x_o - x_j\| \geq r$ for all $j \neq i$. In that case, $\cup_i C(x_i, \theta)$ covers $\mathbb{R}^d$ if and only if $\cup_i S_{x_i, r}$ covers $\{x: \|x\|=1\}$. Then $S_{x_i, r/2}$ are disjoint and $$\cup_i S_{x_i, r/2} \subseteq S_{0,1+r/2} - S_{0, r/2}$$.

Let $v_d := volume(S_{0,1})$. Then $$\gamma_d v_d (r/2)^d \leq v_d (1+r/2)^d - v_d (r/2)^d$$ i.e. $$\gamma_d \leq (1+2/r)^d - 1 = (1+\frac{1}{\sin(\theta/2)})^d-1.$$

Questions:

1. According to the statement of the lemma, does $\gamma_d$ depend on the value of $\theta$ in $(0, \pi/2)$? If not, is it correct that $$\gamma_d \leq \inf_{\theta \in (0, \pi/2)} (1+\frac{1}{\sin(\theta/2)})^d-1?$$
2. In the proof, why $\cup_i S_{x_i, r/2} \subseteq S_{0,1+r/2} - S_{0, r/2}$? If it is true, then isn't $r/2+r/2 \leq 1$ i.e. $r \leq 1$? But this is not true when $\theta > \pi/3$, since $r = 2\sin(\theta/2)$.

3. What does this lemma actually say verbally or geometrically or intuitively?

4. Does the constant $\gamma_d$ have something to do with the kissing number in $\mathbb{R}^d$? Note that a kissing number is defined as the number of non-overlapping unit spheres that touch another given unit sphere.

Thanks and regards!

-

1. Yes, of course $\gamma_d$ depends on $\theta$. If $\theta$ is very small your cones are very narrow and it will take a lot of them to cover all of ${\mathbb R}^d$.

2. Since $\|x_i\| = 1$ by assumption, the triangle inequality says that if $y \in S_{x_i,r/2}$, i.e. $\|y - x_i\| \le r/2$, then $r/2 \le \|y\| \le 1 + r/2$.

3. It's saying that you can cover the unit sphere with at most $\gamma_d$ balls of radius $r$ centred at points on the sphere. The cones generated by those balls (with vertex at the origin) then cover all of ${\mathbb R}^d$. The centres of those balls can be obtained by taking a maximal collection of disjoint balls of radius $r/2$ with centres on the sphere, because if there was a point of the sphere not covered by the balls of radius $r$, the ball of radius $r/2$ centred at that point would be disjoint from the others.

4. For $r = 1$, I guess.

-
+1. Thanks! 2. $\|x_i\| \leq \|y\| + \|x_i-y\|$, so $1 - r/2 \leq \|y\|$. Why is $r/2 \leq \|y\|$? –  Tim May 3 '12 at 2:32
Hmm, yes, that looks like a slip-up. Typo? It should be $1 - r/2$. So then $\gamma_d \le (2/r + 1)^d - (2/r - 1)^d = (1 + 1/\sin(\theta/2))^d - (1 - 1/\sin(\theta/2))^d$ –  Robert Israel May 3 '12 at 5:26
For 3, I don't understand what you said yet, nor what the lemma says. (1) The least number for $\gamma_d$ occurs when the $S_{x_i,r}$'s cover $\{x: \|x\|=1\}$ exactly, isn't it? (2) And there is no upper bound on $\gamma_d$, the bigger it is, the more likely $\{x: \|x\|=1\}$ will be covered. Then why "you can cover the unit sphere with at most γd balls of radius r centred at points on the sphere"? –  Tim May 3 '12 at 12:34
(3) I feel difficult to picture and understand "The centres of those balls can be obtained by taking a maximal collection of disjoint balls of radius r/2 with centres on the sphere, because if there was a point of the sphere not covered by the balls of radius r, the ball of radius r/2 centred at that point would be disjoint from the others." Maybe some rephrasing will help? Thanks! –  Tim May 3 '12 at 12:34
(4) in the proof, for $\cup_i S_{x_i, r/2} \subseteq S_{0,1+r/2} - S_{0, r/2}$ to be true, is $\|x_o - x_j\| \geq r$ for all $j \neq i$ not the right condition, but $\theta \in (0, \pi/3]$ is? –  Tim May 3 '12 at 15:20