While reading textbooks on convex geometry, I heard about Fritz John's theorem on convex body, which is known as John's Theorem or John's Decomposition.
(I know that there are many variants, but this version is from Theorem 2.1 in Löwner–John Ellipsoids by Martin Henk.)
Theorem: Let $K \subset \mathbb R^n$ be a convex body contained in an Euclidean ball $B_n$. Then the following statements are equivalent:
- $B_n$ is the unique minimal volume ellipsoid containing $K$.
- There exist contact points $\mathbf u_1, \cdots , \mathbf u_m \in \mathtt{bd}\ K ∩ \mathtt{bd}\ B_n$, i.e., lying in the boundary of $K$ and $B_n$, and positive numbers $\lambda_1, \cdots , \lambda_m$, $m \geq n$, such that \begin{equation*} \sum_{i=1}^m \lambda_i \mathbf u_i = \mathbf 0 \quad \text{and} \quad \mathbf I_n = \sum_{i=1}^m \lambda_i(\mathbf u_i \mathbf u_i^T) \end{equation*} where $\mathbf I_n$ is the $n\times n$ identity matrix.
I also know that there are upper bound on the number of contact points $m$ -- it's $n(n + 3)/2$ for general convex body $K$ and $n(n + 1)/2$ when $K$ is symmetric in the origin.
I want to apply this famous theorem to my research but I want an algorithmic version of this theorem. How can we actually compute these $m$ contact points from a convex body $K$? Is there any work on the algorithmic version of John's Theorem?
Update: After reading the answer by Joseph O'Rourke below, I see that computing the minimal volume ellipsoid is NP-hard. But I'm interested in computing $m$ contact points in John's Theorem when the convex body $K$ and the minimal volume ellipsoid $B_n$ are known.
For example, consider $K=[-1,1]^n$ which is a centered cube in $\mathbb R^n$ whose edge length is 2. Then $K$ and a Euclidean ball of radius $\sqrt 2$ has $2^n$ contact points as all the vertices of the cube lie at the boundary of the ball. Once we regard these $2^n$ contact points as vectors $\mathbf u_1,\cdots,\mathbf u_{2^n}$, one can easily see that \begin{equation*} \sum_{i=1}^{2^n} \mathbf u_i = \mathbf 0 \quad\text{and}\quad \sum_{i=1}^{2^n} \mathbf u_i \mathbf u_i^T = 2^n \mathbf I_n. \end{equation*} By setting $\lambda_i = 1/2^n$, we see that these contact points satisfy the condition 2 in John's theorem.
But we know that these $2^n$ contact points are too many and we can pick at most $n(n+1)/2$ of them while satisfying the condition 2 by appropriately chosen scaling parameter $\lambda_i$'s. And my question is as follows:
Given a convex body and ellipsoid in $\mathbb R^n$, how can we pick these $m$ contact points that satisfy the condition 2 in John's Theorem?
or maybe as a starting point,
Given a cube $K=[-1,1]^n$ and a Euclidean ball of radius $\sqrt{2}$, how can we pick at most $n(n+1)/2$ vertices of $K$ that satisfy the condition 2 in John's Theorem?
