Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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.

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.