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:
- 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? $
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)$.
What does this lemma actually say verbally or geometrically or intuitively?
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!