Test for intersection of two N-dimensional ellipsoids Let's say I have two $N$-dimensional ellipsoids:
$$ \sum_{i=1}^{N} \frac{(x_i - b_i)^2}{c_i^2} = 1 $$
$$ \sum_{i=1}^{N} \frac{(x_i - b'_i)^2}{c_i'^2} = 1 $$
How can I tell if the two intersect? Is there a computationally easy way to do this test?
 A: I think you can reduce this to a convex optimization problem. The problem is a feasibility problem in which you ask if there is a point $x$ such that $(x-x_a)^T A (x-x_a) \le 1$ and $(x-x_b)^T B (x-x_b) \le 1$, where $A$ and $B$ are the quadratic forms related to the ellipsoids, and $x_a$ and $x_b$ are their centers. These types of problems can be solved efficiently, but typically require a large programming library for implementing them.
A: There are two cases:
(a) One ellipsoid is fully contained in the other.
(b) I think if (a) is not true, then there are always border points from both ellipses in the intersection set. So you can search for strict equality:
$$ \sum_{i=1}^{N} \frac{(x_i - b_i)^2}{c_i^2} = 1 $$
$$ \sum_{i=1}^{N} x_i^2 = 1 $$
(here I simplified by linear transform, so that the second ellipse is a unit n-sphere).
Then you can use $$x_1 = \sqrt{1 - \sum_{i=2}^{N} x_i^2} $$ from the second equation in the first yielding
$$ \sum_{i=2}^{N} \frac{(x_i - b_i)^2}{c_i^2} + \frac{(\sqrt{1 - \sum_{i=2}^{N} x_i^2} - b_1)^2}{c_1^2} = 1$$
This equation has n-1 variables, but is not a polynomial.
Expanding the second term, and multiplying the whole thing by $c_1^2$
$$ c_1^2 \cdot \sum_{i=2}^{N} \frac{(x_i - b_i)^2}{c_i^2} +  1 - \sum_{i=2}^{N} x_i^2 - 2\cdot \sqrt{1 - \sum_{i=2}^{N} x_i^2}\cdot b_1 + b_1^2 = c_1^2 $$
$$ \left( \frac{c_1^2 \cdot \sum_{i=2}^{N} \frac{(x_i - b_i)^2}{c_i^2} +  1 - \sum_{i=2}^{N} x_i^2 + b_1^2 - c_1^2}{2\cdot b_1}\right)^2 = 1 - \sum_{i=2}^{N} x_i^2$$
The last equation is equivalent to finding a root of a n-1 dimensional polynomial.
If (a) is the case, then there are no solutions.
