Closed form solutions for maximal subsets of convex polytopes

Question

I'm looking for any known exact results about inscribing simple convex bodies inside a convex polytope. The most famous is the Löwner-John ellipsoid, but as far as I understood in general there is no closed form solution to this problem. Are there some particular cases, when a solution is known explicitly (maybe not necessarily an ellipsoid, a ball, for example, will do as well) under some extra conditions?

Thank you in advance

Update: cancelled something stupid that I've written before

Answer 1

By Ivan's request, I describe here two algorithms for finding the maximum-size ball contained in a given $n$-dimensional convex polytope $P$. The first algorithm, requiring central symmetry of $P$, provides a solution in one step only, the second one is recursive, and may not produce the solution in finitely many steps, but yield a sequence of approximations instead, converging to a solution. Also, note that the solution is not always unique, as certain convex polytopes, even among the centrally-symmetric ones, contain infinitely many maximum-size balls. Example: any rectangle with unequal sides.

It is best to begin with the so-called H-descripton of $P$, as the intersection of a finite collection of half-spaces, see https://en.wikipedia.org/wiki/Convex_polytope and the references given there. Let $H_1, H_2, \ldots H_k$ denote the boundary (hyper)planes of the half-spaces.

For centrally-symmetric polytopes:

Assume the origin $O$ is the center of symmetry of $P$, therefore $k$ is even and the boundary planes come in pairs reflected about $O$. The radius of the largest ball contained in $P$ is $$ r_{\rm max}=\min_{1\le i\le k} \{{\rm dist}(O,H_i)\},$$ which is easy to compute.

$\ $

For non-symmetric polytopes:

Step 1. Pick a point $c_0$ in the interior of $P$ and compute $\displaystyle r_0=\min_{1\le i\le k} \{{\rm dist}(c_0,H_i)\}$, similarly as above. The ball $B_0$ centered at $c_0$ and of radius $r_0$ is contained in $P$, and it touches the boundary of $P$ at at least one but at most $k$ points on different facets of $P$. If the set $S_0$ of points of contact between $B_0$ and the boundary of $P$ does not lie in any open hemisphere of the boundary of $B_0$, then the ball $B_0$ is the largest ball contained in $P$. Otherwise do:

Step 2. Denote the open hemisphere of $B_0$ that contains the set $S_0$ by $D_0$. Then let $E_0$ be the hyperplane containing $c_0$ and disjoint from $D_0$. Now move the ball $B_0$ perpendicularly to $E_0$ and away from $D_0$ to a new position $B'_0$ by a small translation, small enough to make sure that $B'_0$ is contained in the interior of $P$ and let $c_1$ denote the center of $B'_0$.

Now repeat Step 1 taking $c_1$ in place of $c_0$ and getting $B_1$ and $r_1>r_0$ in place of $B_0$ and $r_0$.

Continue recursively until the set of points of contact of $B_m$ with the boundary of $P$ does not lie in any of the open hemispheres of the boundary of $B_m$. The ball $B_m$ is then the maximum-size ball contained in the polytope $P$.