6
$\begingroup$

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?

  • 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.2011-08-03

2 Answers 2

4

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.

1

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.