I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ball of radius $1-\frac{\theta_d}{2}$ included in the intersection $\bigcap_i B(c_i,r_i)$ where $\theta_d/2 = \frac{1}{2}\sqrt{\frac{2d}{d+1}}$ denotes the ratio between the diameter and the radius of the smallest enclosing ball of a regular simplex.

Intuitively, it seems that the way of making the smallest intersection is to assign all points $c_i$ to the vertices of a regular simplex of diameter $1$ and all $r_i$ to $1$. By doing so, one can check that the ball of radius $1-\frac{\theta_d}{2}$ centered at $x$ the barycenter of $\{c_1,\dots,c_n\}$ is included in the intersection of balls $ \bigcap_i B(c_i,r_i)$. Indeed, in the case of a simplex, the radius of the biggest ball centered at $x$ and included in the intersection of balls is $1-\text{Radius}(\sigma) = 1 - \frac{\theta_d}{2}$ (hence the constant is tight in this case).

I am having difficulties to prove that this case is indeed the worst case. I was just able to prove that the result holds when all balls have the same radius. Does this result seems familiar to someone? I would really appreciate any comment, idea or reference.

ps : The topology tag is here for several reason. One of them is that the biggest radius of the ball included in the intersection corresponds to the weak feature size of the complement of the intersection. Another one is that this result is linked to a collapsibily result.


OK, let's try.

First, $n=d+1$ (Helly's theorem).

Second, if the balls of radii $r_i-\theta_d$ do not have a common point, there is $\theta<\theta_d$ such that the balls of radii $r_i-\theta$ have exactly one common point, say, the origin. Also, we can ignore the balls such that $0$ is not on their boundary. Thus, we get $m\le d+1$ vectors $v_i$ of length $r_i-\theta$ with $|v_i-v_j|\le \min(r_i,r_j)$. Moreover, the vectors $v_i$ cannot lie in one half-space (otherwise there would be more common points), so $\sum_i a_iv_i=0$ for some $a_i\ge 0$, not all of them $0$.

Now just note that as soon as the angle between $v_i$ and $v_j$ is obtuse, decreasing each length keeping $|v_i-v_j|$ constant will increase the angle and that in the case of the equilateral triangle, setting $r_i=1$ will also increase the angle. Thus, if $e_i$ are unit vectors in the directions of $v_i$, we have $\langle e_i,e_j\rangle> -1/d$ and we still have $\sum b_i e_i=0$ with $b_j\ge 0$. However, the matrix with $1$'s on the diagonal and off-diagonal terms satisfying $0>A_{ij}>-1/d$ is positive definite. We thus run into a contradiction.

I hope this holds water. Check everything and let me know if there are any gaps. :)

| cite | improve this answer | |
  • $\begingroup$ Regarding the first (okay, second) sentence: assume $d = 2$. Certainly, we can construct $4$ balls whose intersection contains all the centers, but so that the intersection of any $3$ is strictly larger than the intersection of all $4$. Therefore, the largest ball which fits into the intersection of $3$ will almost surely not fit into the intersection of all $4$. How can we use Helly's theorem to just restrict attention to $d+1$ balls?? $\endgroup$ – Vidit Nanda May 29 '13 at 6:24
  • $\begingroup$ The question is equivalent to asking if the intersection of the balls of_radii $r_i-\theta_d$ (in my notation, I just realized that the OP used $\theta_d/2$ where I used $\theta_d$) is non-empty. $\endgroup$ – fedja May 29 '13 at 10:50
  • $\begingroup$ @fedja Thank you for your answer. I don't understand the last paragraph and the transformation you described. "decreasing each length keeping $|v_i−v_j|$ constant", can you explain me what length you are mentioning here? $\endgroup$ – geoalgo May 29 '13 at 12:43
  • 1
    $\begingroup$ All I wanted to say is that if $\theta$ is less that the radius you want, then in every triangle OIJ with $|OI|=r_i-\theta$, $|OJ|=r_j-\theta$, $|IJ|\le \min(r_i,r_j)$, the angle $O$ is at most as large as that in the triangle with $|OI|=|OJ|=1-\theta$, $|IJ|=1$. $\endgroup$ – fedja May 29 '13 at 18:03
  • $\begingroup$ Now I have it :) Thank you, I really appreciate your help. $\endgroup$ – geoalgo May 31 '13 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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