Given a polytope described by linear inequalities $Ax \le b, x \in \mathbb R^n$, how do you find out if there exist a (non degenerate) sphere of dimension $n-1$ contained in the polytope?


Thanks!



How to find out if a polytope contains a sphere?
If the polytope is less than full dimensional, it is contained in one of the hyperplanes $a\_i \cdot x = b\_i$, where $a\_i$ is a row of $A$ and $b\_i$ the corresponding entry of $b$. You can tell whether this is the case (for 
a particular $i$) by linear programming: minimize $a\_i \cdot x$ subject to 
$Ax \le b$. The polytope is contained in the hyperplane iff the optimal objective value is $b\_i$. 


