Separators for Intersection Graphs of Spheres

Set $V_1=V$. Given a vertex set $V_i$, let ${𝒳}_i$ be a $c$-balanced separator of $G[V_i]$ of size at most $s$. Define $V_{i+1}$ to be the set of vertices comprising the largest connected component of $G[V_i]\setminus {𝒳}_i$. By definition, $|V_{i+1}|\le c|V_i|$. Furthermore, each other connected components of $G[V_i]\setminus {𝒳}_i$ contains at most $\frac{1}{2}|V_i|\le \frac{2}{3}|V|$ vertices. Halt the process at the first $i=r$ satisfying $|V_{r+1}|\le \frac{2}{3}|V|$, so $r\le \lceil {\log }_c(2/3)\rceil$. Defining $𝒳={𝒳}_1\cup \mathrm{\cdots }\cup {𝒳}_r$, we have $|𝒳|\le rs\le \lceil {\log }_c(2/3)\rceil s$. Furthermore, every connected component of $G\setminus 𝒳$ is either equal to $V_{r+1}$, or is a connected component of $G[V_i]\setminus {𝒳}_i$ other than $V_{i+1}$ for some $i$. Since all of these sets have size at most $\frac{2}{3}|V|$, this implies that $𝒳$ is a balanced separator for $G$. $◀$

We will give a randomized procedure that produces a $(1-5^{-d})$-balanced separator $𝒳$ for $G(ℬ)$ of the desired size. By Lemma 2.5, losing another constant factor depending only on $d$, this suffices to prove the desired result.

Let $B_0$ be the ball in ${ℝ}^d$ with smallest radius that contains at least $5^{-d}n$ centers of balls of $ℬ$. ($B_0$ is not necessarily an element of $ℬ$.) By perturbing $B_0$ slightly, one can see that $B_0$ contains exactly $\lceil 5^{-d}n\rceil$ centers. After translating and rescaling the problem appropriately, assume that $B_0=B(1)$, the origin-centered ball of radius 1.

For some $r\in [1,2]$, let $𝒳$ be the set of balls $B\in ℬ$ which intersect the origin-centered sphere of radius $r$. We claim that for any $r\in [1,2]$, the set $𝒳$ is a $(1-5^{-d})$-balanced separator for $G(ℬ)$. To see this, note that each connected component of $ℬ\setminus 𝒳$ consists of balls which are either entirely inside $B(r)$ or entirely outside $B(r)$. Since $B(1)\subseteq B(r)$ contains $\lceil 5^{-d}n\rceil$ centers, there are at most $(1-5^{-d})n$ balls entirely outside $B(r)$. Now $B(2)\supseteq B(r)$ can be covered by $4^d$ translates of $B(1)$ which, by the minimality of $B_0$, each contain at most $\lceil 5^{-d}n\rceil$ centers. Thus $B(2)$ contains at most $4^d\lceil 5^{-d}n\rceil \le (1-5^{-d})n$ centers, so there are at most this many balls entirely inside $B(r)$.

We now show that there is a choice of $r\in [1,2]$ so that $𝒳$ is small. To do this, pick $r\in [1,2]$ uniformly at random. We now bound the expected size of $𝒳$. We do this by modifying $ℬ$ by shrinking those balls that intersect $B(2)$ so that they lie entirely in $B(2)$. For each $B\in ℬ$ which intersects $B(2)$, let ${\mathrm{\ell }}_B$ be the line that passes through the origin and the center of $B$. Let $B^{\prime }$ be the ball contained in $B(2)$ whose center lies on ${\mathrm{\ell }}_B$ and which satisfies ${\mathrm{\ell }}_B\cap B^{\prime }={\mathrm{\ell }}_B\cap B\cap B(2)$. (See Figure 1.) Define ${ℬ}^{\prime }$ to be the set of these balls $B^{\prime }$ (the balls in $ℬ$ that do not intersect $B(2)$ do not have any corresponding ball in ${ℬ}^{\prime }$).

Since each ball $B^{\prime }\in {ℬ}^{\prime }$ lies inside the corresponding ball $B\in ℬ$, clearly we have $p_{{ℬ}^{\prime }}(B^{\prime })\le p_{ℬ}(B)$. Write $p(x)$ for the number of balls of ${ℬ}^{\prime }$ which contain the point $x$. Then $p_{{ℬ}^{\prime }}(B)={\max }_{x\in B}p(x)$. We now have

Thus, dividing by $\mathrm{vol}(B(1))$, we conclude that

Now for each $B\in ℬ$, the probability that $B$ is in the separator is at most the length of the interval ${\mathrm{\ell }}_B\cap B\cap B(2)$. In particular, the probability is 0 if $B$ does not intersect $B(2)$. Now if $B$ does intersect $B(2)$, it corresponds to a ball $B^{\prime }\in {ℬ}^{\prime }$ so that ${\mathrm{\ell }}_B\cap B\cap B(2)={\mathrm{\ell }}_B\cap B^{\prime }$ is an interval of length $2r(B^{\prime })$. Thus by Hölder’s inequality we conclude

$◀$

Let ${𝒮}^{\prime }\subseteq 𝒮$ be the set of spheres containing $p$ in their interior. For any two spheres $S,S^{\prime }\in {𝒮}^{\prime }$, either they intersect or one contains the other in its interior. Consider the partial order on ${𝒮}^{\prime }$ defined by containment. Take any linear extension of this poset and let $S_0\in {𝒮}^{\prime }$ be the median element of this linear extension. This means that there are at least $s-1$ spheres which either intersect $S_0$ or are contained in its interior and there are at least $s-1$ spheres which either intersect $S_0$ or contain it in their interior.

Now let $𝒳=N(S_0)$, the neighborhood of $S_0$ in $G(𝒮)$, i.e., the set of spheres which intersect $S_0$. We claim that every connected component of $G(𝒮)\setminus 𝒳$ has size at most $|𝒮|-s$. To see this, note that no sphere in $𝒮\setminus 𝒳$ intersects $S_0$, so any connected component of $G(𝒮)\setminus 𝒳$ consists of spheres either entirely inside $S_0$ or entirely outside $S_0$. However, we showed that there are at least $s$ spheres that are not of the first type ($S_0$ and the $s-1$ spheres which follow it in the linear extension) and at least $s$ spheres that are not of the second type. Thus each connected component of $G(𝒮)\setminus 𝒳$ has size at most $|𝒮|-s$. $◀$

Set

Choosing $c_d>0$ small in terms of $d$ and $C_d$ large in terms of $c_d$, we will construct a $(1-c_d)$-balanced separator for $G(𝒮)$ of size at most $\mathrm{\Sigma }$. By Lemma 2.5, losing another constant factor depending only on $d$, this suffices to prove the desired result. Assume , since the result is trivial otherwise.

Through the proof, if we have not already found the desired separator, we will define sets ${𝒳}_i\subset 𝒮$ for $i=1,2,3,4$ with $|{𝒳}_i|\le \mathrm{\Sigma }/4$ for each $i$ so that ${𝒳}_1\cup {𝒳}_2\cup {𝒳}_3\cup {𝒳}_4$ is the desired separator.

First, define ${𝒳}_1\subset 𝒮$ to be the $\mathrm{\Sigma }/4$ vertices of highest degree in $G(𝒮)$. Let $\mathrm{\Delta }$ be the maximum degree of the resulting graph $G(𝒮)\setminus {𝒳}_1$. We claim that $\mathrm{\Delta }\le \mathrm{\Sigma }/4$ and $\mathrm{\Delta }\le c_{d}n$. If the first does not hold, then $G(𝒮)$ would have at least $\mathrm{\Sigma }/4$ vertices of degree at least $\mathrm{\Sigma }/4$, meaning that

Clearly this is impossible for $C_d>4$. Similarly, if the second fails then $G(𝒳)$ would have at least $\mathrm{\Sigma }/4$ vertices of degree at least $c_{d}n$, meaning that

where the final inequality holds since . Again, this is impossible for $C_d$ sufficiently large in terms of $c_d$.

Write ${𝒮}_1=𝒮\setminus {𝒳}_1$. The goal of this step is to pass to a subset ${𝒮}_2\subseteq {𝒮}_1$ such that every sphere $S\in {𝒮}_2$ contains fewer than $4c_{d}n$ centers of spheres in ${𝒮}_2$. Let $S_0\in {𝒮}_1$ be a sphere of minimal radius that contains $4c_{d}n$ centers of spheres in ${𝒮}_1$. (If no such sphere exists, taking ${𝒮}_2={𝒮}_1$ completes this step.) Define ${𝒮}_{\supseteq S_0}\subseteq {𝒮}_1$ to be the set of spheres which contain $S_0$ entirely within their interior. First suppose that $|{𝒮}_{\supseteq S_0}|\ge 2c_{d}n$. In this case we can apply Lemma 3.2 to find a separator ${𝒳}_2\subset {𝒮}_1$ such that $|{𝒳}_2|\le \mathrm{\Delta }\le \mathrm{\Sigma }/4$ and each connected component of $G({𝒮}_1)\setminus {𝒳}_2$ has size at most $(1-c_d)n$. Then ${𝒳}_1\cup {𝒳}_2$ is a $(1-c_d)$-balanced separator for $G(𝒮)$ of size at most $\mathrm{\Sigma }/2$.

Thus we can assume that . In this case, define ${𝒳}_2=N(S_0)$, the neighborhood of $S_0$ in $G(𝒮)$. Define ${𝒮}_2\subseteq {𝒮}_1$ to be the set of spheres which are entirely contained within $S_0$. Clearly $|{𝒳}_2|\le \mathrm{\Delta }\le \mathrm{\Sigma }/4$.

Every connected component of $G(𝒮)\setminus ({𝒳}_1\cup {𝒳}_2)$ is either made up of spheres entirely inside $S_0$ or entirely outside $S_0$. The former are also connected components of $G({𝒮}_2)$ while the latter are not. There are at least $4c_{d}n$ centers of spheres of ${𝒮}_1$ inside of $S_0$. Since at most $2c_{d}n$ of these correspond to spheres surrounding $S_0$ and at most $\mathrm{\Delta }$ correspond to spheres which intersect $S_0$, we see that there are at least $2c_{d}n-\mathrm{\Delta }\ge c_{d}n$ spheres inside $S_0$. Therefore any connected component outside of $S_0$ has size at most $(1-c_d)n$. $\mathrm{⊲}$

We now construct a separator for $G({𝒮}_2)$. We know that every sphere in ${𝒮}_2$ contains fewer than $4c_{d}n$ centers of spheres in ${𝒮}_2$. We can also assume that $|{𝒮}_2|\ge (1-c_d)n$, otherwise ${𝒳}_1\cup {𝒳}_2$ is already the desired $(1-c_d)$-balanced separator.

Let $B_{\mathrm{in}}$ be a ball of minimal radius which contains at least $4c_{d}n$ centers of spheres in ${𝒮}_2$. Since we showed that no sphere in ${𝒮}_2$ contains $4c_{d}n$ centers, we see that no sphere in ${𝒮}_2$ contains $B_{\mathrm{in}}$ entirely in its interior. This means that each of the $4c_{d}n$ spheres whose centers lie in $B_{\mathrm{in}}$ also intersect $B_{\mathrm{in}}$.

Write $R$ for the radius of $B_{\mathrm{in}}$ and define $B_{\mathrm{out}}$ to be the ball with the same center and radius $2R$. By the minimality of $B_{\mathrm{in}}$, we see that $B_{\mathrm{out}}$ contains at most $4^d\lceil 4c_{d}n\rceil$ centers. In particular, choosing $c_d$ sufficiently small, there are at least $c_{d}n$ sphere centers outside of $B_{\mathrm{out}}$. Let $S_{\mathrm{rand}}$ be a sphere with the same center as $B_{\mathrm{in}}$ and $B_{\mathrm{out}}$ whose radius is chosen uniformly at random in $[R,2R]$.

For a sphere $S\in 𝒮$, write $r(S)$ for the radius of $S$. Write $\tilde{r}(S)$ for the radius of the spherical cap formed by intersecting the ball bounded by $S$ with $S_{\mathrm{rand}}$. (The radius of a spherical cap is the minimal $\tilde{r}(S)$ so that the cap is contained in a ball of radius $\tilde{r}(S)$.)

Choose some $C_d^{\prime }$ sufficiently large in terms of $d$ and let ${𝒳}_3$ consist of the spheres $S\in {𝒮}_2$ which intersect $S_{\mathrm{rand}}$ and which satisfy $\tilde{r}(S)\le C_d^{\prime }R{(\mathrm{deg}(S)/\mathrm{\Sigma })}^{1/(d-1)}$.

We need to upper bound the probability that a sphere $S$ intersects $S_{\mathrm{rand}}$ in a spherical cap of radius at most $\tilde{r}$. If $\tilde{r}\le r(S)$, the probability is upper bounded by

To see this, note that this event is the same as the event that $S_{\mathrm{rand}}$ intersects the line connecting the center of $B_{\mathrm{in}}$ and the center of $S$ in one of the bold segments in Figure 2.

Now if $\tilde{r}>r(S)$, the probability we need to upper bound is just the probability that $S_{\mathrm{rand}}$ and $S$ intersect. This quantity is at most .

Since ${𝒳}_3$ is defined with the cutoff $\tilde{r}=C_d^{\prime }R{(\mathrm{deg}(S)/\mathrm{\Sigma })}^{1/(d-1)}$, for each $S\in {𝒮}_2$ we have the bound

This implies that

where the equality is by the definition of $\mathrm{\Sigma }$ and the last inequality holds for $C_d$ chosen appropriately large in terms of $C_d^{\prime }$. $\mathrm{⊲}$

Fix some choice of $S_{\mathrm{rand}}$ for which $|{𝒳}_3|\le \mathrm{\Sigma }/4$.

Define ${𝒮}_3={𝒮}_2\setminus {𝒳}_3$. We perform the following iterative process. Start with ${𝒳}_4=\mathrm{\varnothing }$ and ${𝒮}_4={𝒮}_3$. We will define spheres $S_1,S_2,\mathrm{\dots },S_{\mathrm{\ell }}$. Suppose we have defined $S_1,\mathrm{\dots },S_{i-1}$. Define $S_i$ to be a sphere in ${𝒮}_4$ which intersects $S_{\mathrm{rand}}$ and has maximal radius among such spheres. Place the neighborhood $N(S_i)$ in ${𝒳}_4$ and remove all spheres which intersect the ball bounded by $S_i$ from ${𝒮}_4$ (in particular we remove $S_i$ and $N(S_i)$ from ${𝒮}_4$). Repeat until no more spheres in ${𝒮}_4$ intersect $S_{\mathrm{rand}}$.

We claim that the balls bounded by $S_1,S_2,\mathrm{\dots },S_{\mathrm{\ell }}$ are disjoint. For we know that $r(S_i)\ge r(S_j)$ and the ball bounded by $S_i$ is disjoint from the sphere $S_j$. The latter implies that $S_i,S_j$ do not intersect and that $S_i$ does not contain $S_j$; the former implies that $S_j$ does not contain $S_i$.

By the definition of ${𝒳}_3$, every sphere $S\in {𝒮}_3$ which intersects $S_{\mathrm{rand}}$ also satisfies $\tilde{r}(S)>C_d^{\prime }R{(\mathrm{deg}(S)/\mathrm{\Sigma })}^{1/(d-1)}$. Thus

Now since the balls bounded by $S_1,\mathrm{\dots },S_{\mathrm{\ell }}$ are disjoint, we have

where ${\tau }_k,{\sigma }_k$ denote the $k$-volume of the unit ball in ${ℝ}^k$ and the $(k-1)$-volume of the unit sphere in ${ℝ}^k$, respectively. (In the above inequality, we use the fact that the $(d-1)$-volume of a spherical cap of radius $\tilde{r}$ on any sphere in ${ℝ}^d$ is at least the $(d-1)$-volume of a ball of radius $\tilde{r}$ in ${ℝ}^{d-1}$.) Thus we conclude that

where the last inequality holds for $C_d^{\prime }$ chosen sufficiently large in terms of $d$. $\mathrm{⊲}$

By Claim 3.3, it suffices to show that each connected component of $G({𝒮}_2)\setminus ({𝒳}_3\cup {𝒳}_4)$ has size at most $(1-c_d)n$. Note that any sphere in ${𝒮}_2\setminus ({𝒳}_3\cup {𝒳}_4)$ which crosses $S_{\mathrm{rand}}$ must lie in the ball bounded by one of the $S_i$. Furthermore, no sphere in ${𝒮}_2\setminus ({𝒳}_3\cup {𝒳}_4)$ crosses any of the $S_i$. Therefore any connected component of $G({𝒮}_2)\setminus ({𝒳}_3\cup {𝒳}_4)$ must either lie entirely within some sphere $S_i$, entirely within $S_{\mathrm{rand}}$, or entirely outside of $S_{\mathrm{rand}}$. We chose ${𝒮}_2$ so that any sphere in ${𝒮}_2$ contains at most $4c_{d}n$ centers of spheres in ${𝒮}_2$. Thus the first type of connected component has size at most $4c_{d}n$. For the second type, note that $S_{\mathrm{rand}}$ is contained within $B_{\mathrm{out}}$ which we argued earlier contains at most centers of spheres in ${𝒮}_2$. For the third type of connected component, we know that there are at least $4c_{d}n$ spheres which intersect $B_{\mathrm{in}}$. Since $B_{\mathrm{in}}$ is contained in the interior of $S_{\mathrm{rand}}$, we see that there are at most $(1-4c_d)n$ spheres outside of $S_{\mathrm{rand}}$, giving the desired bound on the third type of connected component. $\mathrm{⊲}$ Since $|𝒳|\le \mathrm{\Sigma }$, this completes the proof. $◀$

Intersection graphs of spheres are an example of semialgebraic graphs. Using known bounds on the number of edges in $K_{t,t}$-free semialgebraic graphs [21], we deduce the following weak bound for separators in $K_{t,t}$-free sphere intersection graphs.

Represent the sphere centered at $x\in {ℝ}^d$ with radius $r$ by the point $(x,r)\in {ℝ}^{d+1}$. Now two spheres $(x,r)$ and $(x^{\prime },r^{\prime })$ intersect if and only if ${(r-r^{\prime })}^2\le {\Vert x-x^{\prime }\Vert }^2\le {(r+r^{\prime })}^2$. These are polynomial inequalities of degree $O(1)$, meaning that $G(𝒮)$ can be represented by a semialgebraic graph in ${ℝ}^{d+1}$ of total degree $O(1)$. (See [21, Definition 1.1] for the full definition.)

By [21, Theorem 1.6] (a bound on the Zarankiewicz problem for semialgebraic graphs), if $G(𝒮)$ is $K_{t,t}$-free, then it has $O_d(t^{2/(d+2)}{n}^{2(d+1)/(d+2)})$ edges. Applying Theorem 1.1 with this bound shows that $G(𝒮)$ has a balanced separator of size

$◀$

We can bootstrap this weak bound to get a better bound on the number of edges in a $K_{t,t}$-free sphere intersection graph. This follows from [6, Lemma 8] which turns a bound on the size of separators into a bound on the number of edges for any hereditary family of graphs. (See [8, Section 3] for another application of this method.)

We aim to apply [6, Lemma 8]. This result requires a monotone function $\varphi$ so that any $n$-vertex $K_{t,t}$-free intersection graph of spheres in ${ℝ}^d$ contains a balanced separator of size at most $n\varphi (n)$. By Corollary 3.7, we can take $\varphi (n)=C_d{(t/n)}^{2/d(d+2)}$ where $C_d$ is the constant in that result. Clearly $\varphi (n)$ is monotone.

Set $n_0={(12C_d)}^{d(d+2)/2}t$ so that $\varphi (n_0)=1/12$. Then [6, Lemma 8] implies that every $K_{t,t}$-free intersection graph of spheres in ${ℝ}^d$ on $n\ge n_0$ vertices has at most $C{n}_{0}n/2$ edges where

We can bound

As $n_0=O_d(t)$, this geometric series sums to $O_d(1)$, showing that $C=O_d(1)$. This gives the desired bound on the number of edges when $n\ge n_0$.

Note that if , then we can trivially bound the number of edges by . $◀$

Combining Theorem 1.1 and Corollary 3.8, we immediately conclude the following strengthening of Corollary 3.7. This result improves upon the sphere separator result of Davies–Georgakopoulos–Hatzel–McCarty [3, Theorem 1], proving a strengthening of [3, Conjecture 20].

Let $V={\{1,\mathrm{\dots },k\}}^d$ for $k=\lfloor n^{1/d}\rfloor$. Define $G=(V,E)$ where $x,y\in V$ are adjacent if $\Vert x-y\Vert \le r$. Choosing $1\le r={\mathrm{\Theta }}_d({(m/n)}^{1/d})$ appropriately, we can ensure that $G$ has ${\mathrm{\Theta }}_d(m)$ edges. Note that $G$ is both the intersection graph of the radius $r/2$ balls centered at the points of $V$ and the intersection graph of the radius $r/2$ spheres centered at the points of $V$. We will show that every balanced separator of $G$ has size at least ${\mathrm{\Omega }}_d(m^{1/d}{n}^{1-2/d})$.

We first handle the case when $r=1$. Suppose that $𝒳$ is a balanced separator with $|𝒳|\le k^d/3$. Let $A\subset V$ be the union of some connected components of $G\setminus 𝒳$, satisfying $k^d/3\le |A|\le 2k^d/3$. When $r=1$, the graph $G$ is known as the grid graph on ${\{1,\mathrm{\dots },k\}}^d$. Then the isoperimetric inequality on the grid graph [2] implies that there are at least $k^{d-1}$ edges between $A$ and $V\setminus A$. However, all such edges must have one endpoint in $𝒳$. Since the maximum degree of $G$ is $2d$, we conclude that $|𝒳|\ge k^{d-1}/2d\ge {\mathrm{\Omega }}_d(n^{1-1/d})$, as desired.

To handle the general case, let $r^{\prime }=r/(2\sqrt{d})$. For simplicity, assume that $r^{\prime }$ is an integer that divides $k$, say $k=r^{\prime }{k}^{\prime }$. Divide ${\{1,\mathrm{\dots },k\}}^d$ into ${(k^{\prime })}^d$ subcubes of side length $r^{\prime }$. Note that every vertex in one subcube is adjacent in $G$ to every vertex in an adjacent subcube. Similar to before, suppose that $𝒳$ is a balanced separator with $|𝒳|\le k^d/12$ and $A$ is a union of connected components of $G\setminus 𝒳$ with $k^d/3\le |A|\le 2k^d/3$. Write $B=V\setminus (𝒳\cup A)$. We know $|B|\ge k^d/4$. Define $A^{\prime }\subseteq {\{1,\mathrm{\dots },k^{\prime }\}}^d$ where a point lies in $A^{\prime }$ if the corresponding $r^{\prime }\times \mathrm{\cdots }\times r^{\prime }$ subcube of ${\{1,\mathrm{\dots },k\}}^d$ contains at least one point of $A$. Define $B^{\prime }\subseteq {\{1,\mathrm{\dots },k^{\prime }\}}^d$ similarly. First note that $A^{\prime }$ and $B^{\prime }$ are disjoint – if they shared a vertex then $A,B$ would contain points in the same subcube which have distance at most .

Write $X^{\prime }={\{1,\mathrm{\dots },k^{\prime }\}}^d\setminus (A^{\prime }\cup B^{\prime })$. Note that $|A^{\prime }|\ge |A|/{(r^{\prime })}^d\ge {(k^{\prime })}^d/3$ and similarly $|B^{\prime }|\ge |B|/{(r^{\prime })}^d\ge {(k^{\prime })}^d/4$. Thus $|A^{\prime }|\le {(k^{\prime })}^d-|B^{\prime }|\le 3{(k^{\prime })}^d/4$. Applying the isoperimetric inequality to the grid graph on ${\{1,\mathrm{\dots },k^{\prime }\}}^d$, we conclude that there are at least ${(k^{\prime })}^{d-1}$ edges between $A^{\prime }$ and $B^{\prime }\cup X^{\prime }$. However, there are no edges between $A^{\prime },B^{\prime }$ because any two points in two adjacent subcube are at distance at most $2\sqrt{d}{r}^{\prime }=r$. Thus we conclude that $|X^{\prime }|\ge {(k^{\prime })}^{d-1}/(2d)$. Note though that a point lies in $X^{\prime }$ only if the corresponding subcube lies entirely in $𝒳$. We thus see that $|𝒳|\ge {(r^{\prime })}^d{(k^{\prime })}^{d-1}/(2d)={\mathrm{\Theta }}_d(m^{1/d}{n}^{1-2/d})$. $◀$

Our main results on ball and sphere separators, Theorems 2.2 and 3.1, hold for more general classes of geometric objects. We say that a set $B\subset {ℝ}^d$ is $C$-fat if $B$ contains a ball of radius $r$ and is contained inside a ball of radius $Cr$ for some $r$. Our results hold for fat convex bodies and for the boundaries of fat convex bodies. (See [11, 4] for related results under slightly different hypotheses.)

For each $B\in ℬ$, pick an arbitrary point $p\in \mathrm{int}(B)$ that we call the center of $B$. With this definition, we proceed with the proof of Theorem 2.2 in the same way. The same randomized procedure produces a $(1-5^{-d})$-balanced separator.

For each $B\in ℬ$, let $x_B\subset {ℝ}_{⩾0}$ be the set of radii $r$ so that the origin-centered sphere of radius $r$ intersects $B$. We wish to show that if $x_B\cap [1,2]$ is non-empty, $B$ contains a genuine ball $B^{\prime }$ which is contained in $B(2)$ such that $r(B^{\prime })\ge {\mathrm{\Omega }}_C\left(|x_B\cap [1,2]|\right)$.

First, if $x_B\subseteq [0,2]$, then $B$ is contained in $B(2)$. Now $B$ contains a point of norm $\max (x_B)$ and a point of norm $\min (x_B)$, i.e., it contains two points at distance at least $\max (x_B)-\min (x_B)\ge |x_B|$. This means that any ball containing $B$ must have radius at least $|x_B|/2$. By hypothesis, $B$ contains a ball of radius $|x_B|/2C$. Letting $B^{\prime }$ be this ball, we are done since in this case $B^{\prime }\subseteq B$ is contained in $B(2)$.

Now suppose $x_B⊈[0,2]$, but $x_B\cap [0,2]\ne \mathrm{\varnothing }$. By the same argument, $B$ contains some ball (say $\tilde{B}$) of radius $(\max (x_B)-\min (x_B))/2C$ centered at some point $p$ with $\Vert p\Vert \le \max (x_B)$. By assumption, $B$ contains a point $q$ with $\Vert q\Vert =\min (x_B)\le 2$. (See Figure 3.) Then the convexity of $B$ implies that $B$ contains the convex hull of $\{q\}\cup \tilde{B}$. Elementary geometry implies that this convex hull contains a ball $B^{\prime }$ of radius $\frac{2-\min (x_B)}{2C+1}\ge \frac{|x_B\cap [1,2]|}{2C+1}$ that is contained in $B(2)$. (To see this, dilate the convex hull of $\{q\}\cup \tilde{B}$ by a factor of $(2-\Vert q\Vert )/(\Vert p\Vert +r(\tilde{B})-\Vert q\Vert )$ so that it lies within $B(2)$.)

Thus we have constructed a set ${ℬ}^{\prime }$ contained in $B(2)$ so that $𝔼[|𝒳|]\ge {\mathrm{\Omega }}_C\left({\sum }_{B\in {ℬ}^{\prime }}r(B)\right)$. Note that ${ℬ}^{\prime }$ consists of genuine balls, so the rest of the proof applies unchanged. $◀$