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
    +1. Thanks! 2. $\|x_i\| \leq \|y\| + \|x_i-y\|$, so $1 - r/2 \leq \|y\|$. Why is $r/2 \leq \|y\|$?2012-05-03
  • 0
    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$2012-05-03
  • 0
    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"?2012-05-03
  • 0
    (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!2012-05-03
  • 0
    (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?2012-05-03
  • 0
    OK, I'll try putting it another way. You want to cover the sphere $S = \{x: \|x\|=1\}$ with a finite number of balls of radius $r$ centred at points of $S$. You might try adding balls one-by-one: if your current collection of balls doesn't cover the sphere, add a new ball centred at a point that is not covered (and thus has distance $> r$ from all the centres of your current collection).2012-05-03
  • 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