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?