Largest ball guaranteed to fit in a bounded polyhedron of volume $V$

geometry

Suppose that I have some polyhedron $F \subset [0,1]^d$ (the figure is convex and lies in a bounded unit cube in $d$-dimensional space). The figure also has a positive volume $V > 0$. My question is, what is the largest value of $a \ge 0$ such that a ball (in $\mathbb{R}^d$) of radius $a \cdot V$ is guaranteed to fit inside $F$?

An easy upper bound is $a \le 1/2$, because for an $V \times 1 \times 1 \times \cdots \times 1$ box, one can fit at most a $V/2$ radius ball inside. But perhaps there are other polyhedra that make this worse. Is there any guarantee that $a > 0$?

Best Answer

I have no idea about any upper bound. However, for $d = 2$, $a$ is bounded from below by $\frac14$.

There is a result by Hadwiger${}^{\color{blue}{[1]}}$:

Let $K_1, K_2 \subset \mathbb{R}^2$ be two convex regions bounded by simple closed curves. Let $A_1, A_2$ be their area and $L_1, L_2$ be their perimeter. If following condition is satisfied, $$2\pi(A_1 + A_2) \ge L_1L_2\tag{*1}$$ then one can translate/rotate $K_2$ to make either $K_1$ contains $K_2$ or $K_2$ contains $K_1$.

Let $K_1$ be your $F$ and $L$ be its perimeter. Since $[0,1]^2$ is convex and $F \subset [0,1]^2$, we have $V \le 1$ and $L \le 4$.

Let $K_2$ be a circle of radius $r \le \frac{V}{4}$. Since

$$2\pi(A_1 + A_2) = 2\pi(V+\pi r^2) \ge 2\pi V \ge 8\pi r \ge L(2\pi r) = L_1L_2$$ Condition $(*1)$ is satisfied. Since $A_2 = \pi r^2 \le \frac{\pi}{16}V^2 < V = A_1$, it is impossible to make $K_2$ contains $K_2$. Hadwiger's result tell us one can translate/rotate $K_2$ to make $K_1 = F$ contains $K_2$.

Since this is true for all $F$, we can conclude $a$ is bounded from below by $\frac14$.

Update

It turns out there is a more elementary derivation of a lower bound that can be generalized to higher dimensions. For simplicity of argument, we will assume $F$ is a closed polytope.

For $k \in \mathbb{Z}_{+}$ and geometric shapes $S \subset \mathbb{R}^d$, let $\mu_k(S)$ be the $k$-dim measure of $S$ whenever that make senses.

Let $\mathcal{X}$ be the collection of convex polytopes which are closed, bounded and has non-empty interior. It is known that any $X \in \mathcal{X}$ is a finite intersection of closed half-spaces. More precisely, let $\mathcal{F}$ be the set of facets of $X$. For each facet $f$, let $p_f$ be a point on $f$ and $n_f$ be the outward pointing unit normal vector. For any $s$, define $$H_f(s) = \{ x \in \mathbb{R}^d : n_f \cdot (x - p_f) \le s \} \quad\text{ and }\quad X(s) = \bigcap_{f \in \mathcal{F}} H_f(s)$$

For sufficiently small $s$, $X(s) \in \mathcal{X}$. In particular $X = X(0)$.

Let $\begin{cases} V(s) = \mu_d(X(s))\\ A(s) = \mu_{d-1}(\partial X(s)) \end{cases}$ be the hyper-volume/area of $X(s)$.

In particular, $V = V(0)$ and $A = A(0)$ are the hyper-volume/area of $X$.

Since $X$ is bounded, one can show

  • $V(s)$ is finite, increasing and Lipschitz continuous on $(-\infty,0]$.
  • $R = \sup \{ r : V(-r) > 0 \}$ is finite and $> 0$.

Furthermore, $V(s)$ is differentiable on $(-R,0)$ with $\frac{d}{ds}V(s) = A(s)$

Notice for $s \le 0$, $X(s) \subset X(0) = X$ and both of them are convex, we also have $A(s) \le A$ ${}^{\color{blue}{[2]}}$.

By continuity, we have $V(-R) = 0$. Combine these, we find

$$R \ge \frac1{A}\int_{-R}^0 A(s) ds = \frac1{A}\int_{-R}^0 \frac{d}{ds}V(s)ds = \frac{V(0) - V(-R)}{A} = \frac{V}{A} $$

Back to our original problem and let $X$ be your $F$.

Since $F \subset [0,1]^d$ and both $F$ and $[0,1]^d$ are convex, we have${}^{\color{blue}{[2]}}$

$$A = \mu_{d-1}(\partial F) \le \mu_{d-1}(\partial [0,1]^d) = 2d$$

For $r = \frac{V}{2d}$, we have $$r \le \frac{V}{A} \le R\quad\implies\quad X(-R) \subset X(-r)$$

We claim that $X(-R) \ne \emptyset$. If that is the case, we have $X(-r) \ne \emptyset$ and we can take a $p \in X(-r)$ and the ball centered at $p$ with radius $r$ lies completely within $F$. Since this is true for all $F$, we can conclude:

$a$ is bounded from below by $\frac{1}{2d}$ in higher dimensions.

What's remain is to justify $X(-R) \ne \emptyset$. To see this, consider the function $$\varphi(x) = \inf\left\{ |y-x| : y \not\in X \right\}$$ It is easy to see $\varphi(x)$ is continuous over $X$. Since $X$ is compact, $\varphi(x)$ achieve maximum value $R_*$ at some $p_* \in X$. It is impossible for $R_* < R$ or we can move $p_*$ around to increase $\varphi(\cdot)$. This implies

$$R_* \ge R \implies p_* \in X(-R_*) \subset X(-R) \implies X(-R) \ne \emptyset$$

Notes

  • $\color{blue}{[1]}$, see $\S$ 1.7.6 of Santaló, L., & Kac, M. (2004). Integral Geometry and Geometric Probability (2nd ed., Cambridge Mathematical Library). doi:10.1017/CBO9780511617331

  • $\color{blue}{[2]}$ - We are using the result

    Given $X, Y \subset \mathcal{X}$. If $X \subset Y$, then $\mu_{d-1}(\partial X) \le \mu_{d-1}(\partial Y)$.

    This can be proved using the higher dimension generalization of Cauchy's surface area formula (see $\S 13.2$ of Santaló's book ) which relate the hyper-area $\mu_{d-1}(\cdots)$ with the angular average of projected areas.

Related Question