Prueba para la intersección de dos elipsoides N-dimensional

Question

Digamos que tengo dos $N$-elipsoides dimensionales:

$$ \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 $$

¿Cómo puedo saber si los dos se cruzan? ¿Hay una forma computacionalmente fácil hacer esta prueba?

Answer 1

Creo que esto puede reducir a un problema de optimización convexa. El problema es un problema de viabilidad en el que preguntar si hay un $x$ tal que $(x-x_a)^T A (x-x_a) \le 1$ y $(x-x_b)^T B (x-x_b) \le 1$, donde $A$ y $B$ son las formas cuadráticas relacionadas con elipsoides y $x_a$ y $x_b$ son sus centros. Este tipo de problemas puede ser resuelto eficientemente, pero típicamente requiere una gran biblioteca de programación de aplicación.

Answer 2

Hay dos casos:

(a) un elipsoide está totalmente contenida en la otra.

(b) creo que si (a) no es cierto, siempre hay puntos de frontera de ambos puntos suspensivos en la intersección de conjunto. Así que usted puede buscar la igualdad estricta:

$$ \sum_{i=1}^{N} \frac{(x_i - b_i)^2}{c_i^2} = 1 $$ $$ \sum_{i=1}^{N} x_i^2 = 1 $$ (aquí he simplificado por lineal de transformación, de modo que la segunda elipse es una unidad de n-esfera).

A continuación, puede utilizar $$x_1 = \sqrt{1 - \sum_{i=2}^{N} x_i^2} $$ a partir de la segunda ecuación en la primera rendimiento $$ \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$$

Esta ecuación tiene n-1 variables, pero no es un polinomio.

Ampliando el segundo término, y multiplicando el todo por $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$$

La última ecuación es equivalente a encontrar una raíz de n-1 dimensiones polinomio. Si (a) es el caso, entonces no hay soluciones.