Conditions for when an off-centre ellipsoid fits inside the unit ball 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!
 A: 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.
A: 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.
A: 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.
A: 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.
