3

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$?

PatrickR
  • 4,247
James Siderius
  • 45
  • 1
    What keeps $F$ from being very thin? Then, the ratio of the volumes of biggest sphere inside $F$ and of $F$ goes to $0$, i.e. there is no such $a>0$. – Aaron Goldsmith Jan 05 '23 at 20:43
  • 1
    Notice that F is bounded inside $[0,1]^d$. So you cannot be arbitrarily thin on any dimension otherwise the volume would tend to zero, given the other dimension lengths are bounded between 0 and 1. (I agree with you that if $F$ is just in $\mathbb{R}^d$ that $a = 0$). – James Siderius Jan 05 '23 at 20:53
  • Indeed, the volume would tend to $0$ as it becomes thin. Yet, it can become thin and remain in the cube. Take the box $[0,c]\times [0,1]^{d-1}$. The largest sphere has radius $c/2$ making volume proportional to $c^d$ while the volume of the box is just $c$. As $c\to 0$, the ratio of the volumes also goes to $0$. – Aaron Goldsmith Jan 05 '23 at 21:10
  • @AaronGoldsmith the question mixes volume with length; in your example $1/2$ is the value, since ball of radius $c/2 = 1/2 \cdot V$ fits inside box. Question does not mention volume of fitted ball. – Esgeriath Jan 05 '23 at 21:14
  • @AaronGoldsmith, I don't think this is a valid counterexample because the volume of your box goes to zero as $c \rightarrow 0$. It might be easiest to consider just $d = 2$. Then your example is a rectangle with vanishing width and length 1, which has an area of 0. I'm looking for a positive area shape (with area $V >0$) where you cannot fit a very large circle inside of it. – James Siderius Jan 05 '23 at 21:32
  • Instead of a face given by the vertices with $x_n=0$, use a diagonal hypersurface as base, eg the one spanned by the vertices with $x_1+x_2=1$. The shape of height $h\approx0$ with this as base has volume $\approx h\sqrt2$. This gives $\frac1{2\sqrt2}$ as a better upper bound – Hagen von Eitzen Jan 05 '23 at 21:40
  • @HagenvonEitzen, thanks, this is helpful. Two follow-ups:

    (1) Can this upper bound be generalized to $d$ dimensions?

    (2) Are there any thoughts on how to prove the lower bound in two dimensions? I was thinking a region defined between two out-of-phase sine waves with shrinking periods might cause a bottleneck but have not formally worked this out.

     – James Siderius Jan 05 '23 at 21:54
  • @Esgariath, Ah yes radius in terms of volume caught me off guard! – Aaron Goldsmith Jan 05 '23 at 22:10
  • The polyhedron defined as the convex hull of the point $[0,..,0]$ and all points of the form $[0, .., 0, 1, 0, .., 0]$ seems to be the opposite of what you are looking for. It has volume $1/n!$ and fits a ball of radius $1/2\sqrt{n}$. For $n$ large the volume of ball approaches the volume of the polyhedron. – quarague Jan 06 '23 at 07:34

1 Answers1

3

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.

achille hui
  • 122,701
  • Great answer, thank you. A lower bound on $a$ (even if not explicit) for any given $d$ would be most useful, if it's possible to generalize this. – James Siderius Jan 06 '23 at 01:31