Algorithm to determine if a 3D ellipsoid is contained within another?

Solution 1:

Since the two ellipsoid share the same center, then we can take this center to be the origin of the coordinate system, and then the equations of the two ellipsoids will be

$ r^T Q_1 r = 1 $ and $ r^T Q_2 r = 1 $

Diagonalizing $Q_1$ so that $Q_1 = R_1 D_1 R_1^T $, then

$ r^T R_1 D_1 R_1^T r = 1 $

Define $u = D_1^{(1/2)} R_1^T r $ as a change of variable, then $ u^T u = 1$ so that the first ellipsoid is transformed into the unit sphere. Applying the same transformation to the second ellipsoid, we get

$ u^T D_1^{(-1/2)} R_1^T Q_2 R_1 D_1^{(-1/2)} u = 1 $

which is of the form $u^T Q'_2 u = 1 $ with

$Q'_2 = D_1^{(-1/2)} R_1^T Q_2 R_1 D_1^{(-1/2)} $

Now diagonalize $Q'_2$ into $Q'_2 = R' D' R'^T $

Finally compute the diagonal matrix $ D'' = D'^{(-1/2)}$

The diagonal entries of $D''$ are the lengths of the semi-axes of the second ellipsoid after transformation.

If the maximum of the diagonal entries of $D''$ is less than $1$ then the second ellipsoid is totally inside the first ellipsoid. If the minimum of the diagonal entries of $D''$ is greater than $1$ then the second ellipsoid totally contains the first ellipsoid. Otherwise, the two ellipsoids intersect.

Solution 2:

Say both are centered at the origint. The first is given by $Q_1(x) \le 1$, the second by $Q_2(x) \le 1$, where $Q_i$ are quadratic forms. Now, $E_1 \subset E_2$ is equivalent to $$Q_1(x) \le 1 \implies Q_2(x) \le 1$$ and this is equivalent to $$Q_1(x) \ge Q_2(x)$$ for all $x$, or $$(Q_1-Q_2) \succ 0$$ So it's equivalent to: the form $Q_1 - Q_2$ is positive semidefinite.

Note: If the bodies with centers of symmetry $E_1$, $E_2$ are such that $E_1 \subset E_2$, and $E_2$ is convex, then the translate $E_1'$ of $E_1$ to the origin of $E_2$ is still contained in $E_2$.