John ellipsoid

In mathematics, the John ellipsoid or Löwner-John ellipsoid E(K) associated to a convex body K in n-dimensional Euclidean space Rn is the ellipsoid of maximal n-dimensional volume contained within K. The John ellipsoid is named after the German-American mathematician Fritz John.

In 1948, Fritz John proved that each convex body in Rn contains a unique ellipsoid of maximal volume. Thus, each convex body has an affine image whose ellipsoid of maximal volume is the Euclidean unit ball. He also gave necessary and sufficient conditions for this ellipsoid to be a ball.

The following refinement of John's original theorem, due to Keith Ball, gives necessary and sufficient conditions for the John ellipsoid of K to be a closed unit ball B in Rn:

The John ellipsoid E(K) of a convex body K ⊂ Rn is B if and only if B ⊆ K and there exists an integer m ≥ n and, for i = 1, ..., m, real numbers ci > 0 and unit vectors ui ∈ Sn−1 ∩ ∂K such that

$\sum _{i=1}^{m}c_{i}u_{i}=0$ and, for all x ∈ Rn

$x=\sum _{i=1}^{m}c_{i}(x\cdot u_{i})u_{i}.$ A useful fact is that the dilation by factor $n$ of a John ellipsoid contains the convex body.

Applications

• Obstacle Collision Detection 
• Portfolio Policy Approximation