Closed form solutions for maximal subsets of convex polytopes

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?

Update: cancelled something stupid that I've written before

• As you say, a closed-form solution is too much to be expected. But for the problem of maximum-size ball contained in a given convex polytope, even in a piecewise-smooth convex body, there are fairly simple, natural algorithms, especially for the case of centrally-symmetric bodies. Nov 26 '18 at 18:28
• Could you please give some references?
– Ivan
Nov 27 '18 at 11:19
• I'm not sure there is a publication that addresses this specific problem. I can briefly describe the algorithm for you if you want. Nov 27 '18 at 17:42
• Yes, please. You can even post it as an answer, if you want. I don't think that someone else is going to answer.
– Ivan
Nov 28 '18 at 9:07

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

• Sorry for disappearing =) Yes, I've tried this one immediately, but the problem is that I had a simplex defined by the position of its vertices. Or to be more precise I had a family of convex bodies in $\mathbb{R}^n$ parameterized in $\mathbb{R}^n$ and the idea was to try to approximate it by a ball and see how big this ball can get when $n$ goes to infinity (hoping that it would be infinite, which turned out to be not always the case). I could generate as many points as I wanted to create a simplex, but recalculating them using plane representation for all n seemed like too many computations
– Ivan
Jan 28 '19 at 10:51