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

-
So far I've been able to reduce the general problem down to figuring out when an ellipsoid intersects the unit sphere, but I don't know how to finish from there. –  anon Aug 3 '11 at 19:59
I asked myself whether it is the case that if they intersect, then the line segment between their two centers lies entirely within the union of their interiors and boundaries. And the answer to that is no: in some cases it passes through regions in the intersection of their exteriors. –  Michael Hardy Aug 3 '11 at 23:30
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.