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$
4
  • $\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$ Nov 26, 2018 at 18:28
  • $\begingroup$ Could you please give some references? $\endgroup$
    – Ivan
    Nov 27, 2018 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$ Nov 27, 2018 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, 2018 at 9:07

1 Answer 1

2
$\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$
1
  • $\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, 2019 at 10:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .