3
$\begingroup$

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:

  1. $B_n$ is the unique minimal volume ellipsoid containing $K$.
  2. 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?

$\endgroup$
  • $\begingroup$ How is the convex body presented to a computing device? It is a polytope or something more general? $\endgroup$ – Sergei Ivanov Nov 4 '13 at 14:07
  • $\begingroup$ @SergeiIvanov I don't have much background in this field, but I think we can assume that the convex body is represented as a polytope. Maybe, as a starting point, I can assume that the convex body is a cube $(\pm 1, \cdots, \pm 1)\in\mathbb R^n$. Does it make the problem more solvable? $\endgroup$ – Federico Magallanez Nov 4 '13 at 14:10
3
$\begingroup$

It is NP-hard to compute the minimum volume enclosing ellipsoid of a set of points (if the dimension is part of the input). There have been efficient approximation algorithms developed, e.g.,

P. Kumar, E. A. Yildirim. "Minimum-Volume Enclosing Ellipsoids and Core Sets." Journal of Optimization Theory and Applications. July 2005, Volume 126, Issue 1, pp 1-21. (Springer link)

Jiří Matoušek's 2002 book Lectures on Discrete Geometry has a chapter on this topic (Chapter 13: Springer link). That is likely among the best sources.

$\endgroup$

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.