3
$\begingroup$

Can anyone point me to an algorithm for how to efficiently check if a 3D ellipsoid is contained within another one? We can assume their origins are collocated.

I am dealing with covariance ellipsoids constructed from matrices.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you. I have found some notes on this site (for a more general 2D case) that involve the transformation to the unit circle. This is very clearly laid out. Do you have any references you can point me to, by chance? $\endgroup$
    – dingdong
    Dec 15, 2021 at 22:04
  • $\begingroup$ Did you drop some subscripts for $R$ in your equations? $\endgroup$
    – dingdong
    Dec 15, 2021 at 22:17
  • 1
    $\begingroup$ I've corrected that. $\endgroup$ Dec 15, 2021 at 22:19
  • 1
    $\begingroup$ Sorry. I don't have any references I can point you to. $\endgroup$ Dec 15, 2021 at 22:20
4
$\begingroup$

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$.

$\endgroup$
11
  • $\begingroup$ Can you explain the interpretation of $Q_1(x) \leq 1$? Is that just the equation of points within the ellipsoid? $\endgroup$
    – dingdong
    Dec 15, 2021 at 22:55
  • $\begingroup$ I thought $Q_2 \leq 1$ is taken as a given -- so I am not sure I understand the significance of your claim that $Q_1 \leq 1 \implies Q_2 \leq 1$ $\endgroup$
    – dingdong
    Dec 15, 2021 at 23:00
  • 1
    $\begingroup$ Any ellipsoid centered at the origin has an equation of the form $Q(x) \le 1$ ( just divide by a convenient constant to get RHS $=1$). Then you just see whether one quadratic form is $\preceq $ other. $\endgroup$
    – orangeskid
    Dec 15, 2021 at 23:07
  • $\begingroup$ Makes sense, thanks. Just making sure not to miss anything notationally. $\endgroup$
    – dingdong
    Dec 15, 2021 at 23:09
  • $\begingroup$ @dingdong: It would work for pairs of positive definite forms of same degree. But to check that a form of degree $2 k> 2$ is positive semi-definite may be not easy in general. The case of quadratic forms though is standard, check that the difference has positive eigenvalues ( for instance) $\endgroup$
    – orangeskid
    Dec 15, 2021 at 23:23

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.