Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted
  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.

share|improve this answer
    
+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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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