Distance Between Two Ellipsoids

Question

Find the shortest distance between $\begin{align} &\frac{x_1^2}{a_1^2}+...+\frac{x_n^2}{a_n^2}=1\\ &\frac{x_1^2}{a_1^2}+...+\frac{x_n^2}{a_n^2}=2 \end{align}$.

My thinking is when $n=2$, we have two ellipses where the axes of the second are the same as the first scaled by a factor of $\sqrt{2}$. WLOG, assume $|a_1|<|a_2|$. Then the shortest distance would be $|a_1|(\sqrt{2}-1)$. For the ellipsoid case, I would say the shortest distance is $|a_{\text{min}}|(\sqrt{2}-1)$. I don't know how to prove this formally. I thought about using Lagrange multipliers but had difficulties even setting it up. Any suggestions?

Answer 1

In general, the minimum and the maximum distances (with respect to the standard norm $\|\bullet\|$ on $\mathbb{R}^n$) between two $n$-dimensional ellipsoids given by $$A:=\Biggl\{\left(x_1,x_2,\ldots,x_n\right)\in\mathbb{R}^n\,\Big|\,\sum_{i=1}^n\,\frac{x_i^2}{a_i^2}=1\Biggr\}$$ and $$B:=\Biggl\{\left(x_1,x_2,\ldots,x_n\right)\in\mathbb{R}^n\,\Big|\,\sum_{i=1}^n\,\frac{x_i^2}{b_i^2}=1\Biggr\}\,,$$ where $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ are positive real numbers such that $a_i\geq b_i$ for every $i=1,2,\ldots,n$, are $$\min\big\{a_1-b_1,a_2-b_2,\ldots,a_n-b_n\big\}$$ and $$\max\big\{a_1+b_1,a_2+b_2,\ldots,a_n+b_n\big\}\,,$$ respectively. (Of course, the minimum distance is $0$ if there exist $j,k\in\{1,2,\ldots,n\}$ such that $a_j\geq b_j$ and $a_k<b_k$, whilst the maximum distance is still given by the same formula above.) To show this, one only needs to observe that, if $\textbf{u}\in A$ and $\textbf{v}\in B$ are such that $\|\textbf{u}-\textbf{v}\|$ is optimal, then $\textbf{u}-\textbf{v}$ is parallel to the normal vector of $A$ at $\textbf{u}$ as well as the normal vector of $B$ at $\textbf{v}$.

Answer 2

We begin by switching to parametric coordinates.

Recall that expressing in spherical coordinates:

https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates

We have that a general ellipse can be expressed as

$$ \begin{matrix} x_1 = a_1 r \cos(\theta_1) \\ x_2 = a_2 r \sin(\theta_1)\cos(\theta_2) \\ x_3 = a_3 r \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n = a_nr \sin(\theta_1) ... \sin(\theta_{n-1}) \cos(\theta_n)\end{matrix} $$

Now if we let $\theta_n = 0$, then we effectively have a series of equations for the surface of the n-dimensional ellipse given parametrically.

$$ \begin{matrix} x_1 = a_1 r \cos(\theta_1) \\ x_2 = a_2 r \sin(\theta_1)\cos(\theta_2) \\ x_3 = a_3 r \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n = a_nr \sin(\theta_1) ... \sin(\theta_{n-1}) \end{matrix} $$

The equation of the first ellipsoid will be:

$$ \begin{matrix} x_1 = a_1 \cos(\theta_1) \\ x_2 = a_2 \sin(\theta_1)\cos(\theta_2) \\ x_3 = a_3 \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n = a_n \sin(\theta_1) ... \sin(\theta_{n-1}) \end{matrix} $$ The equation of the second ellipsoid then will be

$$ \begin{matrix} x_1 = \sqrt{2} a_1 \cos(\theta_1) \\ x_2 = \sqrt{2} a_2 \sin(\theta_1)\cos(\theta_2) \\ x_3 = \sqrt{2} a_3 \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n =\sqrt{2} a_n \sin(\theta_1) ... \sin(\theta_{n-1}) \end{matrix} $$

Now we wish to show that we minimize the distance between points on each surface. Of course we need not use the "distance" formula from Euclidean space, we can also use the polar distance formula, where naturally it follows that (we can't change $r$ which is fixed to 1 and $\sqrt{2}$) that getting the angles as close as possible, gets the points as close as possible.

Thus points on the exact same angle, would only differ by $\sqrt{2}-1$ and we conclude that is the min distance between the ellipsoids.

Answer 3

Let $\frac{x_1^2}{a_1^2}+\dots+\frac{x_n^2}{a_n^2} = 1$ and $\frac{y_1^2}{a_1^2}+\dots+\frac{y_n^2}{a_n^2} = 2$. Then by Cauchy-Schwarz $$ 1 = \sum\limits_{k=1}^{n}{\frac{y_k^2-x_k^2}{a_k^2}} = \sum\limits_{k=1}^{n}{(y_k-x_k)\frac{y_k+x_k}{a_k^2}}\le\left(\sum\limits_{k=1}^{n}{(y_k-x_k)^2}\right)^{\frac{1}{2}}\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^4}}\right)^{\frac{1}{2}}. $$ Since $a_k^4\ge(\min{|a_i|})^2a_k^2$ for all $k$, it follows that $\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^4}}\right)^{\frac{1}{2}}\le \frac{1}{\min{|a_i|}}\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^2}}\right)^{\frac{1}{2}}$, and applying the triangle inequality to the vectors $\vec{x} = \left(\frac{x_1}{a_1},\dots,\frac{x_k}{a_k}\right)$ and $\vec{y} = \left(\frac{y_1}{a_1},\dots,\frac{y_k}{a_k}\right)$ yields $$ \left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^2}}\right)^{\frac{1}{2}} = \|\vec{x}+\vec{y}\|\le\|\vec{x}\|+\|\vec{y}\| = 1+\sqrt{2}. $$ Hence, $1\le\frac{1+\sqrt{2}}{\min{|a_i|}}\left(\sum\limits_{k=1}^{n}{(y_k-x_k)^2}\right)^{\frac{1}{2}}$, i.e. $\left(\sum\limits_{k=1}^{n}{(y_k-x_k)^2}\right)^{\frac{1}{2}}\ge(\sqrt{2}-1)\min{|a_i|}$.

If we assume w.l.o.g. that $\min{|a_i|} = |a_1|$, then $(x_1,x_2,\dots,x_n) = (a_1,0,\dots,0)$ and $(y_1,y_2,\dots,y_n) = (\sqrt{2}a_1,0,\dots,0)$ attains equality in the above inequality.

Answer 4

Here is a solution using Lagrange multipliers: The key is to note that if $(x,y)$ solves the problem (with $x,y$ being on the two ellipses), then $x$ is a closest point to the '$y$'-ellipse, and $y$ is a closest point to the '$x$'-ellipse.

Let $f(x) = \sum_k ({x_k \over a_k } ) ^2$. Let $E_k = f^{-1} (\{ k \})$, $k=1,2$ The $E_k$ are compact, so we know there are minimisers. Suppose $(x,y)$ is a minimiser with $x \in E_1, y \in E_2$.

Since $y$ minimises the distance to $E_1$, we have $x-y\parallel \nabla f(y)$. Similarly, since $x$ minimises the distance to $E_2$, we have $y-x \parallel \nabla f(x)$.

Hence $\nabla f(y) = \lambda \nabla f(x)$ for some $\lambda$, and so $y = \lambda x$. Since $y \in E_2, x \in E_1$, we find that $\lambda = \sqrt{2}$.

Hence any minimiser $(x',y')$ satisfies $y' = \sqrt{2} x'$. If $x' \in E_1$, we see that $\sqrt{2}x' \in E_2$, hence we can restrict our search to minimising the distance between $x'$ and $\sqrt{2} x'$, with $x' \in E_1$.

That is, we need to solve $\min \{ (\sqrt{2}-1) \|x'\| | x' \in E_1 \}$, and it is clear that the minimising point is a closest point on $E_1$ to the origin. It is clear that if $i$ is such that $|a_i| = \min_k |a_k|$, then $x'=a_i e_i$ is a minimiser, from which we conclude that the minimum distance is $(\sqrt{2}-1) \min_k |a_k|$.