Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

An ellipsoid $E$ has centre $\vec{c}=(c_1,c_2,c_3)$ and semiaxes $t_1$, $t_2$ and $t_3$ aligned with the $x$, $y$ and $z$ axes. What are the necessary and sufficient conditions on $\vec{c}$, $t_1$, $t_2$ and $t_3$ such that $E$ lies inside the unit ball?

For example, we can require that the set of points where the semiaxes meet the ellipsoid surface lie within the unit ball. This gives a set of inequalities such as $(c_1\pm t_1)^2+c_2^2+c_3^2\leq1$, which are necessary but not sufficient. How many points on the surface of the $E$ need to be checked before you know that the whole ellipsoid is within the unit ball? (Clearly, you only need to check the point on the surface of $E$ that is furthest from the origin, but then the problem becomes how to find that point.)

It is easy to formulate a set of inequalities for the special case that the ellipsoid is centred on an axis (i.e. only one $c_i$ is non-zero). However, the off-axis case seems impossible even in 2 dimensions: given an ellipse with centre $\vec c=(c_1,c_2)$ and semiaxes $t_1$ and $t_2$, aligned with the $x$ and $y$ axes, what are the conditions for this to lie within the closed unit disk?

For the 2D case, the solution might go along these lines (as suggested here amongst other places). Parameterise the perimeter of the ellipse as $x = t_1 \cos\phi + c_1$ and $y = t_2 \sin\phi + c_2$. Then any point on the ellipse perimeter has $x^2+y^2=(t_2^2-t_1^2)\sin^2\phi+2t_1c_1\cos\phi+2t_2 c_2 \sin\phi+\mathrm{const}$. Differentiate this expression to find the $\phi$ for which $x^2+y^2$ is maximal, and see if $x^2+y^2\leq1$ for that $\phi$. If any one of the four parameters $c_1$, $c_2$, $t_1$, $t_2$ is zero then this becomes a simple quadratic, but in general it seems to be not analytically possible.

So, my questions are as follows:

  • What are the conditions for an off-axis ellipse to lie within the unit disk?
  • The on-axis ellipse can easily be extended to an on-axis ellipsoid (see Lemma 26 of http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=669165). Is this also true in the off-axis case?
  • (I'm not a mathematician so I don't know whether this is a very deep or a completely worthless question...) If the problem is not analytically tractable, why not? How can such an elementary question be so difficult? This question doesn't sound like Fermat's last theorem - it's just very basic Euclidean geometry.

Thanks very much for any help!

share|improve this question
3  
There are natural questions in "basic Euclidean geometry" that lead to complicated equations that don't have simple solutions. For example, given $5$ general conics $C_1,\ldots,C_5$ in the plane there's finitely many conics $C$ tangent to all of them, but in general finding $C$ requires solving an equation of degree $3264$ $-$ and even the determination of the degree is nontrivial, never mind the equation! See isites.harvard.edu/fs/docs/icb.topic720403.files/book.pdf –  Noam D. Elkies Aug 25 '13 at 5:06
    
Your problem for the ellipse (the 2D case) can be solved analytically, since it leads to a polynomial equation of degree 4, but in higher dimensions finding the most distant point analytically is probably impossible. However, if you just want a "yes-or-no" answer to "is the ellipsoid contained in the ball?", without locating the point, then perhaps it is possible, but could be very hard already in 3D. –  Wlodek Kuperberg Aug 25 '13 at 11:54

4 Answers 4

Note: This is the third version of my answer, one that is, I hope, considerably clearer and cleaner than the previous two.

This can be reduced to a standard problem in real arithmetic, one that, in principle, is solvable, but just how nice the solution will be is a matter of taste, I think.

For simplicity of notation, let me set $\rho_i = 1/t_i^2$ and $\lambda_i = -c_i/{t_i}^2$ for $i=1,2,3$. Also, set $\rho_0 = (c_1/t_1)^2+(c_2/t_2)^2+(c_3/t_3)^2-1$. Consider the following symmetric matrix depending on a parameter $\nu$ $$ Q(\nu) = \begin{pmatrix} \rho_0{+}\nu & \lambda_1 & \lambda_2 &\lambda_3\\ \lambda_1 & \rho_1{-}\nu & 0 & 0\\ \lambda_2 & 0 &\rho_2{-}\nu & 0\\ \lambda_3 & 0 & 0 &\rho_3{-}\nu \end{pmatrix} $$ and set $D(\nu) = \det\bigl(Q(\nu)\bigr)$.

Claims: (1) The ellipsoid $E$ is disjoint from the unit sphere if and only if there is a value of $\nu$ such that $Q(\nu)$ is either positive or negative definite. (2) The ellipsoid $E$ lies in the interior of the unit ball if and only if the quartic equation $D(\nu)=0$ has $4$ real roots $\nu_i$ that satisfy $0<\nu_0<\nu_1\le\nu_2\le\nu_3$ and, moreover, $Q(\nu)$ is positive definite for some (and, hence, all) $\nu$ satisfying $\nu_0<\nu<\nu_1$.

Note that there are well-established tests for when a matrix is positive definite and for when a quartic polynomial has real roots that are positive. How much you know about the constants $\rho_i$ and $\lambda_i$ will determine how hard actually carrying these tests out will be.

Here is the argument for the claims:

Consider the following two quadratic forms on $\mathbb{R}^4$, $$ q = -{x_0}^2+{x_1}^2+{x_2}^2+{x_3}^2 $$ and $$ p = \rho_0\,{x_0}^2 + 2\lambda_1\,x_0x_1+2\lambda_2\,x_0x_2+2\lambda_3\,x_0x_3 + \rho_1\,{x_1}^2+ \rho_2\,{x_2}^2+ \rho_3\,{x_3}^2, $$

To know whether or not the ellipsoid $E$ and the unit sphere have a real intersection point is the same as knowing whether there is a nonzero vector in $\mathbb{R}^4$ that is a null vector for both $q$ and $p$. Now, it is a standard fact of linear algebra that, on a real vector space of dimension greater than $2$, a pair of quadratic forms has a positive definite linear combination if and only if they have no common null vector other than the zero vector. (See the Footnote for a proof of this standard fact.) This establishes the first claim.

The second claim depends on the first: If $E$ (assumed to have nonempty interior) lies in the interior of the unit ball, then $p$ and $q$ have no common null vector, so, by the first claim, there is some value of $\nu$ for which $Q(\nu)$ is definite (either positive or negative). It then follows from the usual linear algebra proofs that $p$ and $q$ can be simultaneously diagonalized, i.e., (since $q$ and $p$ clearly have type $(3,1)$ and $(1,3)$ respectively), there is a basis of $\mathbb{R}^4$ such that, in the corresponding coordinates $y_i$, we have $$ q= -{y_0}^2+{y_1}^2+{y_2}^2+{y_3}^2 $$ and $$ p = -\nu_0\,{y_0}^2+\nu_1\,{y_1}^2+\nu_2\,{y_2}^2+\nu_3\,{y_3}^2 $$ for some (nonzero, since $p$ is nondegenerate) numbers $\nu_i$. Since $E$ is contained in the interior of the unit ball if and only if the closure of the negative cone of $p$ is contained in the negative cone of $q$, it follows that all of the $\nu_i$ must be positive, and, in fact, rearranging $\nu_1,\nu_2,\nu_3$ if necessary, we must have $0<\nu_0<\nu_1\le \nu_2\le \nu_3$. It is now clear that the roots of $D(\nu)=0$ are the $\nu_i$ and that $Q(\nu)$ is positive definite when $\nu_0<\nu<\nu_1$, since $p-\nu q$ is.

Conversely, if $Q(\nu)$ and $D(\nu)$ satisfy the hypotheses, then $p-\nu q$ is a positive definite quadratic form and so the negative cone of $q$ must contain the negative cone of $p$, which implies that $E$ lies in the interior of the unit ball.

Footnote added on 9/1/13: To prove the Standard Fact:

One direction is obvious: If the two quadratic forms have a positive definite linear combination, then they have no common null vector.

For the other direction, let $p$ and $q$ be quadratic forms on $\mathbb{R}^n$ (where $n>2$) that have no common zero other than $0\in\mathbb{R}^n$. We need to show that some linear combination of $p$ and $q$ is positive definite.

Consider the map $f = (p,q):\mathbb{R}^n\to\mathbb{R}^2$, which, by hypothesis, sends only the origin to the origin. The normalized map $$ F(v) = \frac{f(v)}{|f(v)|} $$ is well-defined and smooth on $\mathbb{R}^n$ minus the origin and is even, i.e., $F(v)=F(-v)$, and homogeneous of degree $0$, so it induces a well-defined smooth map $\phi:\mathbb{RP}^{n-1}\to S^1\subset\mathbb{R}^2$.

Now, the image of $S^{n-1}\subset\mathbb{R}^n$ under $f$ lies in an open halfspace in $\mathbb{R}^2$ if and only if some linear combination of $p$ and $q$ is positive definite, so suppose that this (connected) image does not lie in any open halfspace. Then there will exist two nonzero vectors $x,y\in\mathbb{R}^n$ such that $f(x) = - f(y)\not=(0,0)$. Then, by the usual polarization identity for quadratic forms, one has $$ f(\cos\theta\,x+\sin\theta\,y) = \cos2\theta\, f(x) + \sin2\theta\, \tfrac12f(x{+}y)\ \ (\not=0\ \text{for all $\theta$}). $$ This implies that the path $\gamma(t) = [\cos\theta\,x+\sin\theta\,y]$ for $0\le t\le \pi$, which is a closed path in $\mathbb{RP}^{n-1}$ that generates $H_1(\mathbb{RP}^{n-1},\mathbb{Z})\simeq \mathbb{Z}_2$, is mapped by $\phi$ to a generator of $H_1(S^1,\mathbb{Z})\simeq\mathbb{Z}$, which is absurd.

Note that the proof breaks down for $n=2$ because $H_1(\mathbb{RP}^{1},\mathbb{Z})\simeq \mathbb{Z}$ instead of $\mathbb{Z}_2$. This is good because the pair of quadratic forms $p = x^2-y^2$ and $q = 2xy$ on $\mathbb{R}^2$ have no common null vector and yet have no positive definite linear combination.

share|improve this answer
    
Could you please explain why the original question is equivalent to $Q(\nu)>0$? I can see roughly how the argument would go (we want a vector $\vec{v}$ for which $\vec{v}^\mathrm{T}Q\vec{v}>0$ to achieve $x^2+y^2+z^2-1>0$) but don't quite get it exactly. –  Antony Sep 1 '13 at 11:59
    
@Anthony: OK, I'll add this as an addendum to the answer. –  Robert Bryant Sep 1 '13 at 15:53
    
Thanks a lot, that is very helpful. I believe the extension from working out whether $Q(\nu)>0$ to working out whether $Q(\nu)>0$ or $Q(\nu)<0$ is reasonably straightforward. Using your previous notation, let $p_i(\nu)$ denote the determinant of the upper lefthand $i$-by-$i$ minor. Then $Q(\nu)>0$ if and only if $p_i(\nu)>0$ for $i=1,2,3,4$, whilst $Q(\nu)<0$ if and only if $p_i(\nu)>0$ for $i=2,4$ and $p_i(\nu)<0$ for $i=1,3$. –  Antony Sep 1 '13 at 22:14
    
In fact, maybe this even simplifies the test for definiteness, since we only require the product $p_1 p_3>0$ (or equivalently the ratio) rather than the stronger individual conditions $p_1>0$ and $p_3>0$? –  Antony Sep 1 '13 at 22:25
    
@Antony: Actually, I have thought about this a little more and see that the statement can be cleaned up a bit and the ambiguity about the positive or negative definite situation can be removed. I'll modify my answer accordingly. –  Robert Bryant Sep 3 '13 at 17:00

This is just to elaborate on Robert's idea. Once you bring the question to this form, you can show that the matrix is positive definite iff $1\le \nu\le \min\rho_j$ and $$ \nu-1\ge\sum_j\frac{\lambda_j^2}{\rho_j-\nu} $$ (once you fix the first variable, the worst choice for every other one is obvious). Assume $\rho_1\le\rho_2\le\rho_3$ Note that when $\nu$ is near $1$ and near $\rho_1^-$, the RHS is larger, so the corresponding equation must have two roots (counting with multiplicity) on $(1,\rho_1)$. Since we are also guaranteed a root on each of the intervals $(\rho_j,\rho_{j+1})$ ($j=1,2$), we conclude that a certain quartic monic polynomial in $z=1-\nu$ must have four real negative roots, or, in other words, all roots must be real and all coefficients non-negative. The analytic condition for this event is known. There are several equivalent ways to state it. For programming purposes, the description in this paper seems to be the most convenient (you do not need anything beyond the front page; the definitions, etc. can be googled readily). So, you end up with a lot of elementary algebraic manipulations and 6 inequalities. Whether it beats the purely numeric approach is up to you to decide.

share|improve this answer
    
Please not that I noticed an error in my formula for $Q(\nu)$, which changes the tests for positive definiteness. You may want to modify your answer accordingly since it depends on my former incorrect formula. –  Robert Bryant Sep 1 '13 at 21:23

Right you are: "Clearly, you only need to check the point on the surface of $E$ that is furthest from the origin, but then the problem becomes how to find that point."

Now then:

To find the point(s) in question, use Lagrange Multipliers: find point(s) $x$ on the surface $E$ at which the gradient of $E$ is parallel to the vector $x$. There may be up to four such points; find all of them and pick the most distant one from the origin.

share|improve this answer
    
Do you mean four such points for the 3D ellipsoid case? A quick go at this seems to give an equation which is 6th order in terms of a Lagrange multiplier. (That is by maximising $x^2+y^2+z^2$ subject to the constraint $(\frac{x-c_1}{t_1})^2+(\frac{y-c_2}{t_2})^2+(\frac{z-c_3}{t_3})^2-1=0$.) –  Antony Aug 25 '13 at 2:59
    
Assuming no two of the semiaxes are equal, in the plane there will be up to four points; in 3D up to six, and so on. If the equation cannot be solved by hand, there are numerical methods to find approximate solutions. –  Wlodek Kuperberg Aug 25 '13 at 3:20
    
Right, I agree with this. However, does the fact that the equation in 3 dimensions has 6 roots necessarily mean that there is in general no analytic solution to the problem? It seems like there is some redundancy in this method, since it also finds points on the ellipsoid that are closest to the origin. Could there be some more geometric argument for identifying only the most distant points, which would lead to a a lower order equation that can be solved analytically? –  Antony Aug 25 '13 at 9:29

You also ask, How many points on the surface of the ellipsoid $E$ need to be checked before you know that the whole ellipsoid is within the unit ball?

Answer: No finite number of points will suffice. If the ellipsoid's diameter is smaller than 2 (otherwise there is no problem), then there is a spot of positive area on it, say around the end point of the ellipsoid's longest semiaxis, where the radius of the osculating ball is smaller than 1. Then, no matter how many (finitely many, though) points you pick on the ellipsoid's surface, the ellipsoid can be placed so that all the points you picked will lie inside the ball, yet a small spot (a sub-spot of the one mentioned before) will protrude outside the ball.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.