1

I would like to prove an ellipsoid $E_a$ center at $q_a$ with shape matrix $A$ and radius $r_a$ defined as: $(x-q_a)^T A^{-1} (x-qa) <= r_a$

is included into another ellipsoid $E_b$ -i.e. $E_a$ covers $E_b$- defined as $E_a$:

$(x-q_b)^T B^{-1} (x-qb) <= r_b$

with x defined on $R^n$

I was thinking about showing that all points defined by $E_a$ are also included into $E_b$ such that $E_a <= E_b$ but I don't know how to prove a condition satisfying this ellipsoid status. I don't really find paper or information about that ... link Because they target center at the origin ellipsoids.

Thank you a lot for your help and maybe if Jacob see this topic because he asked for the same question without any answers, Regards.

Cedric
  • 11

1 Answers1

1

A possible approach to the problem is first to perform an affine transformation on $R^n$ that takes ellipsoid $E_b$ to the unit sphere. Writing $u$ for the transformed coordinates, we have $$u = \frac1{\sqrt{r_b}} B^{-1/2}(x - q_b).$$ Then $x = \sqrt{r_b} B^{1/2} u + q_b$ and $$x - q_a = \sqrt{r_b} B^{1/2} u + q_b - q_a = \sqrt{r_b} B^{1/2} \left( u - \frac1{\sqrt{r_b}} B^{-1/2}(q_a - q_b) \right).$$ Let $q_0 = \dfrac1{\sqrt{r_b}} B^{-1/2}(q_a - q_b),$ and we can write the equation above more concisely as $$x - q_a = \sqrt{r_b} B^{1/2} (u - q_0).$$

When we substitute the right-hand side of this equation for $x - q_a$ in the equation of ellipsoid $E_a,$ we get $$(u - q_0)^T \left(\sqrt{r_b} B^{1/2}\right)^T A^{-1} \sqrt{r_b} B^{1/2} (u - q_0) \leq r_a,$$ which simplifies to $$(u - q_0)^T B^{1/2} A^{-1} B^{1/2} (u - q_0) \leq \frac{r_a}{r_b}.$$ (Note that $B$ must be symmetric positive definite in order that $(x-q_b)^T B^{-1} (x-q_b) \leq r_b$ may define an ellipsoid, and therefore $(B^{1/2})^T = B^{1/2}.$)

Let $M = \dfrac{r_b}{r_a}B^{1/2} A^{-1} B^{1/2},$ and the problem reduces to a maximization problem in which we want to find $$s = \sup \{ u^T u : (u - q_0)^T M (u - q_0) \leq 1 \}.$$ Then $E_a$ is contained in $E_b$ if and only if $s \leq 1.$

You should be able to find helpful information on the solution of this maximization problem, for example on pages $13$-$14$ of this document.

As an aside, for an ellipsoid defined by $(x-q_b)^T B^{-1} (x-q_b) \leq r_b,$ I think it is misleading to call $r_b$ the "radius" of the ellipsoid. First of all, an ellipsoid does not have a single radius; furthermore, even if we do somehow single out one radius, for example the circumradius, you should find that as you vary $r_b$ in the equation above, the circumradius of the ellipsoid varies in proportion to $\sqrt{r_b},$ not $r_b.$

A more conventional way to write the equation of a general ellipsoid would be $(x-q_b)^T B^{-1} (x-q_b) \leq 1,$ which you can get by scalar multiplication of the matrix you would have used in your original formula. This would simplify the equations in this answer.

David K
  • 98,388
  • First of all, thank you for your clear answer and your time. However, I don't really get why should I solve an optimization problem in this case ? Actually, I know all the parameters of $E_a$ and $E_b$ then I guess I can state about the inclusion of both ellipsoids without solving an optimization problem no ? Probably, I go the wrong way ... – Cedric Sep 29 '18 at 17:46
  • In order to show containment, you need to show that every point of $E_a$ satisfies $(x-q_b)^T B^{-1} (x-q_b) \leq r_b.$ I suppose one might skip the affine transformation and just maximize $(x-q_b)^T B^{-1} (x-q_b)$ over $E_a.$ The reason to look for the maximum is that once you have found it, either it violates $(x-q_b)^T B^{-1} (x-q_b)$ (hence no containment) or it satisfies $(x-q_b)^T B^{-1} (x-q_b)$ (guaranteeing the every other point in $E_a$ does also, hence containment). – David K Sep 29 '18 at 17:59
  • Ok thank you I have gotten it. Another question maybe very "naive": I attempt to reason by sets then I have the feeling if I do the difference of the two sets as Ea-Eb and if this difference is less or equal to 0 then Ea is included into Eb. Actually I am looking for a condition on the set considering that the equation set defines the whole points thus, I guess it is not useful to find the maximum point. First of all, do you think it is possible to handle this problem by this way without any optimization problem ? And second, do you have any tips to recommend me ? Thank you for your time. – Cedric Sep 30 '18 at 08:09
  • There are several inherent difficulties in this problem. One is that you have an infinite number of points in each ellipse, so you will not be able to examine the set difference directly. Another is that the boundaries of the ellipsoids have multiple radii of curvature in arbitrary orientation, so it's possible that all axes of ellipsoid $E_a$ are completely inside $E_b$, even that all the axial-plane sections are inside $E_b$, yet there is some tiny sliver of $E_a$ that barely emerges through the surface of $E_b$. Optimization will find that tiny sliver. I doubt there is an easier way. – David K Sep 30 '18 at 12:44
  • By the way, I'm not saying no other algorithm exists. I'm saying that I fear that any other algorithm would be just as complicated as optimization, if not even more so, because it has to account for all the possible ways one ellipsoid can break through the surface of another. – David K Sep 30 '18 at 13:02