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