Point on an ellipsoid closest to line

Question

The $2D$ case is not a problem:

$$\ P(t) =(x,y)= s + t v = <s_x+tv_x, s_y+tv_y> $$

$$\ F(x,y) = (\frac{x}{a})^2 +(\frac{y}{b})^2 -1 = 0 $$ $$ \nabla F(x,y).v =0 $$

Finally solve for $y$ in terms of $x$, and plug into ellipse equation, $F(x,y)$.

For the $3D$ case, where I have $P(t)= (x,y,z)$ and am now using a $3D$ ellipsoid, the previous method does not work. I am left with more variables than equations. Any advice is appreciated.
$$\ P(t) =(x,y,z)= s + t v = <s_x+tv_x, s_y+tv_y, s_z+tv_z> $$

$$\ F(x,y,z) = (\frac{x}{a})^2 +(\frac{y}{b})^2 +(\frac{z}{c})^2-1 = 0 $$

---

EDIT: Thank you for the feedback.

@ja72: Your solution has been tested and works.

@Semiclassical: I have been looking at Lagrange Multipliers and have an idea for how to solve my problem. The steps below have been tested and work.

(1) Given a line defined by two points $\vec{x1}$ and $\vec{x2}$, $\vec{r}$ , I know the equation for the minimum distance between $\vec{r}$ and a point $\vec{x0}$ $$\ d(x_0,y_0,z_0) = \frac{|(\vec{x0}-\vec{x1})X(\vec{x0}-\vec{x2})|}{|\vec{x2}-\vec{x1}|} $$

(2) Given my constraint that the point $\vec{x0}$ must reside on the ellipse $$\ F(x_0,y_0,z_0) = (\frac{x_0}{a})^2 +(\frac{y_0}{b})^2 +(\frac{z_0}{c})^2-1 = 0 $$

(3) The Lagrange problem is stated below and is solved by following (http://tutorial.math.lamar.edu/Classes/CalcIII/LagrangeMultipliers.aspx):

Find the minimum of $\ d(x_0,y_0,z_0) $ subject to the constraint $\ F(x_0,y_0,z_0) $.

Answer 1

1. A 3D line is defined with 6 Plücker coordinates $L=(\vec{e}, \vec{p}\times\vec{e})$ where $\vec{e}$ is the direction of the line, and $\vec{p}$ is any point along the line.
2. Lemma, The point lies on the plane defined by the origin and the line.
3. The ellipsoid is represented by the 4×4 matrix $$C = \begin{pmatrix} 1/a^2 & 0 & 0 & 0 \\ 0 & 1/b^2 & 0 & 0 \\ 0 & 0 & 1/c^2 & 0 \\ 0 & 0 & 0 & -1 \end{pmatrix}$$ and a point by the homogeneous coordinates $P= (\alpha x,\alpha y,\alpha z,\alpha)$ such that $P^\top C P =0$ gives the familiar equation $\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0$
4. A 3D plane tangent to the ellipsoid through the closest point is perpendicular to the plane defined in (2) above. To find the normal of this plane, we use the vector describing the point on the line closest to the origin. This is given by $$\boxed{\vec{r} = -\dfrac{\vec{e} \times (\vec{e} \times \vec{p})}{|\vec{e}|^2} = (i,j,k)}$$ The homogeneous coordinates of this plane are $W=(i,j,k,-\ell)$ with normal direction $$\vec{n}=\frac{\vec{r}}{|\vec{r}|} = \frac{(i,j,k)}{\sqrt{i^2+j^2+k^2}}$$ and unknown distance from the origin $$d=\frac{\ell}{|\vec{r}|} = \frac{\ell}{\sqrt{i^2+j^2+k^2}}$$
5. To make sure the plane is tangent to the ellipsoid we set $W^\top C^{-1} W =0$ and solve for $$\ell =\sqrt{a^2 i^2 + b^2 j^2 + c^2 k^2}$$.
6. The point on the ellipse where the tangent plane touches (and closest to line) is defined in homogeneous coordinates by $P=C^{-1} W$ $$ P=(\alpha x, \alpha y, \alpha z, \alpha) = (a^2 i,b^2 j,c^2 k,-\ell) $$ $$ \boxed{ \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \dfrac{1}{\sqrt{a^2 i^2+b^2 j^2+c^2 k^2}} \begin{pmatrix} a^2 i \\ b^2 j \\ c^2 k \end{pmatrix} } $$

---

Appendix

The 6 Plüker coordinates of a line through points $\vec{r}_1$ and $\vec{r}_2$ are $$ L = (\vec{r}_2-\vec{r}_1, \, \vec{r}_1 \times \vec{r}_2 ) $$

Answer 2

This equation

$$\nabla F(x,y,z) \cdot \vec{v} = 0$$

limits you to a locus of points on the surface of the ellipsoid, which isn't enough.

You can visualize this by a simple case. Take the line to be parallel to the major axis of the ellipsoid, but displaced from the ellipsoid. Then the gradient equation above will give you that the point lies somewhere on the circle that goes around the ellipsoid midway between the two ends.

Once you have this equation, then you need to determine the point from there that is minimum distance to the line.

Answer 3

You have another condition that the gradient, when extended to a line, must intersect the given line. In other words, there must exist an $\alpha$ and $t$ such that $P(t) = \alpha \nabla F$.

Answer 4

You have the ellipsoid

$ r^T Q r = 1 $

where $ Q = \begin{bmatrix} \dfrac{1}{a^2} && 0 && 0 \\ 0 && \dfrac{1}{b^2} && 0 \\ 0 && 0 && \dfrac{1}{c^2} \end{bmatrix}$

And the line $ p(t) = s + t v $

Now, pick a point $r_1$ on the ellipsoid, and a point $p_1$ on the line, then the displacement vector between them is

$ w = r_1 - p_1 = r_1 - (s + t_1 v ) $

From the well-known properties of the minimum distance, we know that if the pair $r_1$ and $p_1$ form a shortest distance, then their difference (vector $w$) must be perpendicular to the line direction $ v$ and at the same time be along the gradient vector of the ellipsoid at $r_1$.

So the first equation is that

$ v^T ( r_1 - s - t_1 v ) = 0 \tag{1}$

This equation enables us to find $t_1$ in terms of $r_1$

$ t_1 = \dfrac{1}{v^T v} ( v^T (r_1 - s) ) \tag{2}$

And the second condition is that

$ (Q r_1) \times ( r_1 - s - t_1 v) = 0 \tag{3} $

Plug in $t_1$ from $(2)$

$ (Q r_1) \times \bigg( I - \dfrac{v v^T}{v^T v} \bigg) (r_1 - s) = 0 \tag{4} $

Equation $(4)$ is a vector equation, that has three components.

Now recall that if $V$ and $W$ are two vectors, then

$ V \times W = (V_2 W_3 - V_3 W_2 , V_3 W_1 - V_1 W_3 , V_1 W_2 - V_2 W_1 )$

Since $V_i = e_i^T V$ , and $W_j = e_j^T W $, then

$ V \times W = ( V^T (e_2 e_3^T - e_3 e_2^T) W , V^T (e_3 e_1^T - e_1 e_3^T) W , V^T ( e_1 e_2^T - e_2 e_1^T ) W ) \tag{5}$

Define

$E_1 = e_2 e_3^T - e_3 e_2^T $

$E_2 = e_2 e_3^T - e_3 e_2^T $

$ E_3 = e_1 e_2^T - e_2 e_1^T $

Applying $(5)$ to $(4)$,

$r_1^T Q E_1 P (r_1 - s) = 0 \tag{6a}$

$r_1^T Q E_2 P(r_1 - s) = 0 \tag{6b}$

$r_1^T Q E_3 P (r_1 - s) = 0 \tag{6c}$

where $P = I - \dfrac{v v^T}{v^T v} $

only two of these three equations is needed, the third one is dependent.

So taking any two of equations $(6)$, and adding to this system the equation of the ellipsoid, which is

$ r_1^T Q r_1 = 1 \tag{7} $

Gives a system of three quadratic equations in $r_1$ which can be solved using numerical methods. For example, one can write script in Mathematica language or SAGE language to find all the possible solutions $r_1$.

I've worked an example on this SAGE page.

where $ a= 2 , b = 3, c = 4 , s = [11, 13, 17] , v = [1, 1, -2] $

The SAGE script uses Lagrange multiplier method to find the critical points. The results over $\mathbb{R}$ are

$ (x,y,z, t, \lambda) = (-0.65415929, -1.80604058, -2.91368788142, 2.2278625954, -84.88465499485) $

This corresponds to the maximum (perpendicular) distance between a point on the ellipsoid and a point on the line, with a distance of $26.86657783$

and

$ (x,y, z, t, \lambda) = (0.706861036285, 1.7273073989, 2.949106449, 1.08932584269, 64.411330049 ) $

which corresponds to the minimum perpendicular distance between a point on the ellipsoid and a point on the line, with the distance being $20.57498806 $. Since we're seeking the closest points then this our closest distance.

Answer 5

Victor's remark needs one more vector because $\nabla F$ only gives the direction of the gradient, but its starting point is needed too: $P(t) = (x,y,z) + \alpha \nabla F(x,y,z)$. This, together with John's observation, gives us four equations for five unknowns: $(x,y,z,\alpha,t)$. So one more condition is necessary: $F(x,y,z)=0$.