0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wlodek Kuperberg Nov 26 '18 at 18:28
  • $\begingroup$ Could you please give some references? $\endgroup$ – Ivan Nov 27 '18 at 11:19
  • $\begingroup$ I'm not sure there is a publication that addresses this specific problem. I can briefly describe the algorithm for you if you want. $\endgroup$ – Wlodek Kuperberg Nov 27 '18 at 17:42
  • $\begingroup$ Yes, please. You can even post it as an answer, if you want. I don't think that someone else is going to answer. $\endgroup$ – Ivan Nov 28 '18 at 9:07
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Ivan Jan 28 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.