0
$\begingroup$

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 Answers 1

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

  • 0
    Since balls of radius $r/2$ whose centres have distance >r between them are disjoint, and these balls are all in a region with finite volume, the process can't go on too long. When it stops, you have covered the sphere.2012-05-03