Author Русская версия


Distance evaluation between geometric objects

Hereinafter the distance between X=(x_{1},\dots,x_n) and Y=(y_{1},\dots,y_n) from \mathbb R_{}^{n} is defined as:

\sqrt{(x_1-y_1)^2+\dots+(x_n-y_n)^2} \ .

Distance from a point to a linear manifold

Problem. Find the distance from a point X_{0} \in {\mathbb R}^n to a linear manifold \mathbb M_{} in {\mathbb R}^{n} given by a system of linear equations

\left\{ \begin{array}{ccc} c_{11}x_1+c_{12}x_2+\dots+c_{1n}x_n &=& h_1 \\ \dots & & \dots \\ c_{m1}x_1+c_{m2}x_2+\dots+c_{mn}x_n &=& h_m \end{array} \right.

or in matrix form

CX={\mathcal H} \quad where \quad C=\left( \begin{array}{cccc} c_{11}& c_{12} & \dots & c_{1n} \\ \dots & & & \dots \\ c_{m1}& c_{m2} & \dots & c_{mn} \end{array} \right)_{m\times n} ,\ {\mathcal H} =\left( \begin{array}{c} h_1 \\ \vdots \\ h_m \end{array} \right),\ X=\left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right)

It is assumed that m\le n_{} and that \operatorname{rank} (C) = m_{}, i.e. the linear system is consistent and defines the (n-m)-dimensional manifold in {\mathbb R}^{n} .

Th

Theorem 1. [1]. Compose the square matrix of the order m+1_{}:

M=\left( \begin{array}{cc} C\cdot C^{\top} & CX_0- {\mathcal H} \\ (CX_0- {\mathcal H})^{\top} & 0 \end{array} \right)

Distance from X_{0} to the linear manifold equals

d= \sqrt{-\frac{\det M}{\det(C\cdot C^{\top})}} \ .

§

The radicand is nonnegative due to the assumption imposed on the \operatorname{rank} (C)_{} and the properties of the Gram determinant:

\det ( C\cdot C^{\top}) > 0 \ .

=>

Distance from X_{0}=(x_{10},\dots,x_{n0}) to the hyperplane (line if n=2)

c_1x_1+\dots+c_nx_n= h

equals

d= \frac{|c_1x_{10}+\dots+c_nx_{n0}-h|}{\sqrt{c_1^2+\dots+c_n^2}} \ .

The nearest to X_0 point of the hyperplane (line) is:

X_{\ast}=X_0- \frac{c_1x_{10}+\dots+c_nx_{n0}-h}{c_1^2+\dots+c_n^2} \left(\begin{array}{c} c_1 \\ \vdots \\ c_n \end{array} \right) \, .


Let the manifold be represented parametrically as

\mathbb M=\{Y_0+\lambda_1 Y_1+\dots+\lambda_k Y_k \mid \{\lambda_1,\dots,\lambda_{k}\} \subset {\mathbb R} \}

for the given columns \{Y_0,Y_1,\dots,Y_k \}\subset {\mathbb R}^n. Assume these columns to be linearly independent. Compose the following matrices

L=\left[ Y_1|\dots|Y_k \right]_{n\times k} \quad and \quad \tilde L = \left[ Y_1|\dots|Y_k| X_0-Y_0 \right]_{n\times (k+1)}

(here |_{} stands for concatenation).

Th

Theorem 2. Distance from the point X_{0} to the linear manifold \mathbb M equals

d=\sqrt{\frac{\det(\tilde L^{\top}\cdot \tilde L)}{\det( L^{\top}\cdot L)}} \ .

§

The assumption of the linear independency of \{Y_1,\dots,Y_{k} \} results in the positive definiteness of the matrix L^{\top}\cdot L_{} (property of the Gram determinant). The matrix \tilde L^{\top}\cdot \tilde L_{} has the nonnegative determinant for any choice of \{Y_{0},Y_1,\dots,Y_k \}.

§

Last theorem is a particular case of the well-known application of the Gram determinant.

Th

Theorem 3. The nearest to X_0 point in the manifold \mathbb M_{} is given by the formula

X_{\ast}=Y_0+ L(L^{\top}\cdot L_{})^{-1} L^{\top} (X_0-Y_0) \, .

Ex

Example. Find the distance from X_{0}=(1,1,1,1)^{\top} to the manifold

\left\{\begin{array}{rrrrc} 3x_1&+x_2&-x_3&+x_4&=1 \\ x_1 & -2x_2&+x_3&+2x_4&=2. \end{array} \right.

Solution. 1-st method: application of Theorem 1. One has:

C=\left( \begin{array}{rrrr} 3 & 1 & -1 & 1 \\ 1 & -2 & 1 & 2 \end{array} \right), {\mathcal H}= \left( \begin{array}{r} 1 \\ 2 \end{array} \right),
C\cdot C^{\top} = \left( \begin{array}{cc} 12 & 2 \\ 2 & 10 \end{array} \right),\ CX_0=\left( \begin{array}{r} 4 \\ 2 \end{array} \right), \ CX_0-{\mathcal H}=\left( \begin{array}{r} 3 \\ 0 \end{array} \right) \ ,
\frac{\left| \begin{array}{ccc} 12 & 2 & 3 \\ 2 & 10 & 0 \\ 3 & 0 & 0 \end{array} \right|}{\left| \begin{array}{cc} 12 & 2 \\ 2 & 10 \end{array} \right|}=\frac{-90}{116}=-\frac{45}{58} \ .

2-nd method: application of Theorem 2. Find the general solution for the generating system:

x_3=\frac{5}{3}x_1+\frac{4}{3}x_2, \ x_4=1-\frac{4}{3}x_1+\frac{1}{3}x_2 \ .

Thus, the parametric equation of the manifold is as follows

\mathbb M=\{Y_0+\lambda_1 Y_1 + \lambda_2 Y_2 \mid \{\lambda_1,\lambda_2\} \in \mathbb R \} \quad where \quad Y_0 = \left( \begin{array}{r} 0 \\ 0 \\ 0 \\ 1 \end{array} \right),\ Y_1=\left( \begin{array}{r} 0 \\ 3 \\ 4 \\ 1 \end{array} \right),\ Y_2=\left( \begin{array}{r} 3 \\ 0 \\ 5 \\ -4 \end{array} \right) \ .

One gets:

L= \left( \begin{array}{rr} 0 & 3 \\ 3 & 0 \\ 4 & 5 \\ 1 & -4 \end{array} \right), \ \tilde L =\left( \begin{array}{rrr} 0 & 3 & 1 \\ 3 & 0 & 1 \\ 4 & 5 & 1 \\ 1 & -4 & 0 \end{array} \right), \ \frac{\left| \begin{array}{ccc} 26 & 16 & 7 \\ 16 & 50 & 8 \\ 7 & 8 & 3 \end{array} \right|}{\left| \begin{array}{cc} 26 & 16 \\ 16 & 50 \end{array} \right|}=\frac{810}{1044}=\frac{45}{58} \ .

The nearest to X_{0} point in the manifold is as follows:

X_{\ast}= \left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}\right)+\left( \begin{array}{rr} 0 & 3 \\ 3 & 0 \\ 4 & 5 \\ 1 & -4 \end{array} \right)\left( \begin{array}{ccc} 26 & 16 \\ 16 & 50 \\ \end{array} \right)^{-1} \left(\begin{array}{rrrr} 0 & 3 & 4 & 1 \\ 3 & 0 & 5 & -4 \end{array} \right)\left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 0 \end{array}\right)=\frac{1}{58} \left(\begin{array}{c} 16 \\ 37 \\ 76 \\ 49 \end{array}\right) \, .

Result. d=\sqrt{45/58} \approx 0.8808303295_{}.

Distance between linear manifolds

Let the linear manifolds in {\mathbb R}^{n} be given parametrically

\mathbb M_1=\{ X_0+ \lambda_1 X_1+\dots + \lambda_k X_k \quad \mid \quad \{\lambda_1,\dots,\lambda_k \} \subset \mathbb R \}

and

\mathbb M_2=\{ Y_0+\mu_1Y_1+\dots+\mu_{\ell}Y_{\ell} \quad \mid \quad \{\mu_1,\dots,\mu_{\ell} \} \subset \mathbb R \}

for specified columns \{X_0,X_1,\dots,X_k,Y_0,Y_{1},\dots,Y_{\ell}\}\subset {\mathbb R}^n. We will assume these manifolds to be not parallel. Compose the matrices from these columns

P=\left[ X_1|\dots|X_k| Y_1|\dots | Y_{\ell} \right]_{n\times (k+\ell)} \quad u \quad \tilde P = \left[ X_1|\dots|X_k| Y_1|\dots | Y_{\ell}| X_0-Y_0 \right]_{n\times (k+\ell+1)}

(here |_{} stands for concatenation).

Th

Theorem. Distance between linear manifolds \mathbb M_1 and \mathbb M_2 equals

d=\sqrt{\frac{\det(\tilde P^{\top}\cdot \tilde P)}{\det( P^{\top}\cdot P)}} \ .

Remark. Using the Gram determinant properties one has:

\det (P^{\top}\cdot P) > 0 \quad \iff \quad columns \ \{X_1,\dots,X_k,Y_1,\dots,Y_{\ell} \} are linearly independent;
\det(\tilde P^{\top}\cdot \tilde P) \ge 0 \quad for \forall \ \{X_0,X_1,\dots,X_k,Y_0,Y_1,\dots,Y_{\ell} \} \ .
Ex

Example[2]. Find the distance between the manifolds

\left( \begin{array}{r} 89 \\ 37 \\ 111 \\ 13 \\54 \end{array} \right) + \lambda_1 \left( \begin{array}{r} 1 \\ 1 \\ 0 \\ -1 \\ -1 \end{array} \right) + \lambda_2 \left( \begin{array}{r} 1 \\ -1 \\ 0 \\ -1 \\ 1 \end{array} \right) \quad and \quad \left( \begin{array}{r} 42 \\ -16 \\ -39 \\ 71 \\3 \end{array} \right) + \mu_1 \left( \begin{array}{r} 1 \\ 1 \\ 0 \\ 1 \\ 1 \end{array} \right) + \mu_2 \left( \begin{array}{r} 1 \\ -1 \\ 0 \\ 1 \\ -1 \end{array} \right) \ .

Solution.

P^{\top}\cdot P=4\cdot I_{4 \times 4}, \quad \tilde P^{\top}\cdot \tilde P= \left(\begin{array}{ccccc} 4 & 0 & 0 & 0 & 107 \\ 0 & 4 & 0 & 0 & 103 \\ 0 & 0 & 4 & 0 & 93\\ 0 & 0 & 0 & 4 & -115 \\ 107 & 103 & 93 & -115 & 33483 \end{array} \right) \ .

Result. d=150_{}.

Distance from a point to a quadric

Th

Theorem 1. The square of the distance to the quadric {\mathbb R}^{n} given by the equation

X^{\top}AX+2\,B^{\top}X-1=0 \ , (A=A^{\top})

from the point X_{0} \in {\mathbb R}^n not lying in the quadric (i.e. X_{0}^{\top}AX_0+2 B^{\top}X_0-1\ne 0) equals the minimal positive zero of the distance equation

{\mathcal F}(z)={\mathcal D}_{\mu} (\Phi(\mu,z))=0 \ ,

provided that the mentioned zero is not a multiple one. Here

\Phi(\mu,z)=\det \left( \left[ \begin{array}{cc} A & B \\ B^{\top} & -1 \end{array} \right] + \mu \left[ \begin{array}{cc} -I & X_0 \\ X_0^{\top} & z-X_0^{\top}X_0 \end{array} \right] \right)

while {\mathcal D}_{} stands for the discriminant of the polynomial (treated w.r.t. \mu), and I_{} is the identity matrix of the order n_{}.

=>

[3,4]. The square of the distance from {\mathbb O} \in {\mathbb R}^{n} to the quadric in {\mathbb R}^{n} given by the equation

X^{\top}AX+2B^{\top}X-1=0 \ ,

equals the minimal positive zero of the distance equation

{\mathcal F}(z)={\mathcal D}_{\mu} \left( f(\mu)(\mu z-1)-B^{\top}\operatorname{adj}(A,\mu)B \right)=0\ ,

provided that this zero is simple. Here f(\mu)=\det (A-\mu I) is the characteristic polynomial of the matrix A_{} while \operatorname{adj}(A,\mu) is the adjoint matrix for A-\mu I_{}.

=>

For the particular case B={\mathbb O}_{} (i.e. the quadric centered to the origin), one has:

{\mathcal F}(z)=\left[z^nf(1/z) \right]^2{\mathcal D}_{\mu}(f(\mu)) \ ,

and the distance from the origin to the quadric equals 1_{}/\sqrt{\lambda_{\max}}, where \lambda_{\max}^{} stands for the maximal eigenvalue of the matrix A_{}.

Ex

Example. Find the distance from the origin to the ellipsoid

7x_1^2+6x_2^2+5x_3^2-4x_1x_2-4x_2x_3-3x_1-4x_2+5x_3-18=0\ .

Solution. Here

A = \left( {\begin{array}{rrr} \frac{7}{18} & -\frac{1}{9} & 0 \\ && \\ -\frac{1}{9} & \frac{1}{3} & -\frac{1}{9} \\ && \\ 0 & -\frac{1}{9} & \frac{5}{18} \end{array}} \right),\quad B = \left( \begin{array}{r} -\frac{1}{12} \\ \\ -\frac{1}{9} \\ \\ \frac{5}{36} \end{array} \right) ,
f(\mu)=\det (A-\mu I)=-\mu ^{3} + \mu ^{2} - \frac{11}{36} \mu + \frac {1}{36}

The adjoint matrix to A-\mu I:

\operatorname{adj}(A,\mu)= \left( \begin{array}{ccc} \mu ^{2} - \frac{11}{18} \mu + \frac{13}{162} & - \frac{1}{9} \mu + \frac{5}{162} & \frac{1}{81} \\ && \\ - \frac{1}{9} \mu + \frac{5}{162} & \mu^2 -\frac{2}{3}\mu+\frac{35}{324} & - \frac{1}{9} \mu +\frac{7}{162} \\ && \\ \frac{1}{81} & - \frac{1}{9} \mu + \frac{7}{162} & \mu ^{2} - \frac{13}{18}\mu+\frac{19}{162} \end{array} \right) \ .
\Phi(\mu,z)=f(\mu)(\mu z-1)-B^{\top}\operatorname{adj}(A,\mu)B=
=-z \mu ^{4} + (z+1) \mu ^{3} + \left(-\frac {11}{36} z - \frac{673}{648}\right) \mu ^{2} +\left( \frac {1}{36} z + \frac {241}{729} \right) \mu - \frac {1621}{52488} \ .

Utilization of the determinantal representation for the discriminant yields:

{\mathcal F}(z) = {\mathcal D}_{\mu} (\Phi(\mu,z)) = \frac{1}{16} \times
\times \left| \begin{array}{cccccc} 4z & - 3z-3 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} & 0 & 0 \\ &&&&& \\ 0 & 4z & - 3z-3 & \frac{11}{18} z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} & 0 \\ &&&&& \\ 0 & 0 & 4z & - 3z-3 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} \\ &&&&& \\ 0 & 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12} z - \frac{241}{243} & \frac{1621}{13122} \\ &&&&& \\ 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} & \frac{1621}{13122} & 0 \\ &&&&& \\ - z - 1 & \frac{11}{18} z + \frac{673}{324} & - \frac{1}{12} z - \frac{241}{243} & \frac{1621}{13122} & 0 & 0 \end{array} \right| =
=\frac{1}{578415690713088} ( 38263752\,z^6-966487788\,z^5+9376985736\,z^4-43882396481\,z^3+
+102982092872\,z^2-116747905827\,z+50898162294) \quad .

Its real roots are as follows:

z_1 \approx 1.394685033, \ z_2 \approx 5.701814366, \ z_3 \approx 7.043940671,\ z_4 \approx 7.590059711 \quad .

Result. d= \sqrt{z_1} \approx 1.180967837_{}.

§

For the case n=3_{} the problem stated corresponds to the ellipsoid height evaluation known in GPS systems.

To find the nearest point X_{*} in the quadric, one can utilize the following algorithm which we illuminate for the case X_{0}={\mathbb O}:

1. On evaluating (within a prescribed accuracy) the minimal positive root z_{\ast}^{} of the polynomial {\mathcal F}(z), one can restore the corresponding value of \mu_{\ast}^{}. The correspondence should be interpreted in the sence that for the specialization z=z_{\ast}^{} the discriminant of the polynomial

\Phi(\mu,z) = f(\mu)(\mu z-1)-B^{\top}\operatorname{adj}(A,\mu)B

treated w.r.t. \mu_{} vanishes. That means the polynomial \Phi(\mu_{},z_{\ast}) possesses a multiple root which will be denoted \mu_{\ast}^{}. This root can be represented as a rational function of z_{\ast}^{} with the aid of subdiscriminants.

2. The nearest point X_{*} in the quadric is evaluated via the formula:

X_{\ast} = - \frac{1}{f(\mu_{\ast})} \operatorname{adj}(A,\mu_{\ast}) B \ .
Th

Theorem 2. Under the conditions of Theorem 1 , the coordinates of the nearest to the given point X_{0} point X_{\ast}^{} in the quadric, can be found as

X_{\ast}=(\mu_{\ast}E- A)^{-1} (B+\mu_{\ast} X_0) ;

here \mu_{\ast} denotes the multiple zero for the polynomial \Phi(\mu,z_{\ast}).

§

This means: the coordinates of the nearest point in the quadric generically can be expressed as rational functions from the squared distance.

Ex

Example. For the ellipsoid from the previous example, find the point nearest to the origin.

Solution. Substitute z_{}=z_{\ast} \approx 1.394685033 into the formula for the multiple root evaluation:

\mu=-\frac{\left| \begin{array}{cccc} 4z & - 3z-3 & \frac{11}{18} z + \frac{673}{324} & 0 \\ &&& \\ 0 & 4z & - 3z-3 & - \frac{1}{36} z - \frac{241}{729} \\ &&& \\ 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & \frac{1621}{13122} \\ &&& \\ - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} & 0 \end{array} \right|} {\left| \begin{array}{cccc} 4z & - 3z-3 & \frac{11}{18} z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} \\ &&& \\ 0 & 4z & - 3z-3 & \frac{11}{18}z + \frac{673}{324} \\ &&& \\ 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} \\ &&& \\ - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} & \frac{1621}{13122} \end{array} \right|}

One gets \mu_{\ast}^{} \approx 0.5726704086. Substitute now this value into the formula for X_{\ast}^{}:

X_{\ast}=\left(\begin{array}{r} 0.0711706544 \\ -0.8677186523 \\ 0.797924553 \end{array} \right) \ .

Check.

X_{\ast}^{\top} X_{\ast} = \mathbf{1.39468}4515,\ X_{\ast}^{\top}AX_{\ast}+2B^{\top}X_{\ast}-1=2.9\cdot 10^{-7}\ ,

and {\mathbb O}X_{\ast}^{} is normal to ellipsoid at the point X=X_{\ast}^{}:

AX_{\ast}+B=\left(\begin{array}{r} 0.040757326\\ -0.496916796 \\ 0.456947781 \end{array} \right)\approx \mu_{\ast} X_{\ast} \ .
§

Further details for the distance equation {\mathcal F}(z)_{}=0 for the particilar cases \mathbb R^{2} and \mathbb R^{3} are HERE .

Distance from a linear manifold to a quadric

Problem. Find the distance from the ellipsoid in {\mathbb R}^n given by an equation

X^{\top}AX+2B^{\top}X-1=0 \ , (A=A^{\top})

to a linear manifold in {\mathbb R}^n given by a system of linear equations

\left\{ \begin{array}{ccc} c_{11}x_1+c_{12}x_2+\dots+c_{1n}x_n &=& 0 \\ \dots & & \dots \\ c_{m1}x_1+c_{m2}x_2+\dots+c_{mn}x_n &=& 0 \end{array} \right.

or, in matrix form

CX={\mathbb O} \quad where \quad C=\left( \begin{array}{cccc} c_{11}& c_{12} & \dots & c_{1n} \\ \vdots & & & \vdots \\ c_{m1}& c_{m2} & \dots & c_{mn} \end{array} \right)_{m\times n} \, .

We assume that m\le n and that \operatorname{rank} (C) =m i.e. the linear manifold in {\mathbb R}^n is a (n-m)-dimensional one.

Th

Theorem. The ellipsoid intersects the linear manifold iff

0 \le \left| \begin{array}{lrc} A & B & C^{\top}\\ B^{\top} & -1 & {\mathbb O}\\ C & {\mathbb O} & \mathbb{O} \end{array} \right| \times \left\{ \begin{array}{l} (-1)^{m-1} \ if \ A\ is \ \mathbf{positive}\ definite, \\ (-1)^n \ if \ A\ is \ \mathbf{negative}\ definite \end{array} \right.

=>

The vanishement of the determinant from the above theorem provides the necessary and sufficient condition for the existence of the tangency point for the manifolds.

Th

Theorem. If the condition of the previous theorem is not satisfied then the square of the distance from the ellipsoid to the linear manifold equals the minimal positive zero of the polynomial

{\mathcal F}(z) ={\mathcal D}_\mu \left( \mu^m \left| \begin{array}{ccc} A & B & C^{\top}\\ B^{\top} & -1 + \mu z & \mathbb{O}\\ C & \mathbb{O} & \frac{1}{\mu} C \cdot C^{\top} \end{array} \right| \right),

provided that this zero is simple. Here {\mathcal D} stands for the discriminant of the polynomial treated w.r.t. \mu.

=>

If the system of rows of C is an orthonormal one then, by transforming the determinant in the theorem, one can diminish its order: the expression under discriminant can be reduced into

\left| \begin{array}{cc} A-\mu C^{\top} C & B \\ B^{\top} & -1+\mu z \end{array} \right|.

Ex

Example. Find the distance to the x_1-axis from the ellipsoid

7\, x_1^2+6\, x_2^2 +5\, x_3^2 -4\,x_1x_2-4\,x_2x_3-37\,x_1-12\,x_2+3\,x_3+54=0 \ .

Solution. Here

A= \left( \begin{array}{rrr} -\frac{7}{54} & \frac{1}{27} & 0 \\ &&\\ \frac{1}{27} & -\frac{1}{9} & \frac{1}{27} \\ &&\\ 0 & \frac{1}{27} & -\frac{5}{54} \end{array} \right), \ B=\left( \begin{array}{r} \frac{37}{108} \\ \\ \frac{1}{9} \\ \\ -\frac{1}{36} \end{array} \right)

and one can choose

C= \left( \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) \ .

Matrix A is negative definite, therefore the intersection condition is not fulfilled:

\left| \begin{array}{ccc} A & B & C^{\top}\\ B^{\top} & -1 & {\mathbb O}\\ C & {\mathbb O} & \mathbb{O} \end{array} \right| \times (-1)^3 = - \frac{143}{11664} < 0 \ .

Use the Corollary to the theorem:

\left| \begin{array}{cc} A-\mu C^{\top} C & B \\ B^{\top} & -1+\mu z \end{array} \right|=\left| \begin{array}{cccc} -\frac{7}{54} & \frac{1}{27} & 0 & \frac{37}{108} \\ &&&\\ \frac{1}{27} & -\frac{1}{9}-\mu & \frac{1}{27} & \frac{1}{9} \\ &&&\\ 0 & \frac{1}{27} & -\frac{5}{54}-\mu & -\frac{1}{36} \\ &&&\\ \frac{37}{108} & \frac{1}{9} & -\frac{1}{36} & -1 + \mu z \end{array} \right| =
=-\frac{7}{54}z \mu^3+\left(-\frac{73}{2916}z+\frac{143}{11664}\right)\mu^2+\left(-\frac{1}{972}z-\frac{1069}{314928}\right)\mu-\frac{1621}{4251528}

and the discriminant of this polynomial w.r.t. \mu equals

{\mathcal F}(z)=\frac{1}{13493281232954916864} \times
\times \left(1331935488\,z^4-38807307008\,z^3+245988221152\,z^2-1086769525104\,z+61289436065 \right)

Positive zeros of this polynomial are 0.05712805,\ 22.54560673.

Result. d \approx \sqrt{0.05712805} \approx 0.23901475.

Remark. For the general case, one gets \deg {\mathcal F}(z) = 2m, i.e. the degree of {\mathcal F}(z) equals the doubled number or linear equations yielding the manifold. For the particular case m=1, one gets quadric equation:

=>

The distance from

c_1x_1+\dots+c_nx_n = h \ \iff \ CX=h

to the nearest and to the farthest points on the ellipsoid

X^{\top}AX+2B^{\top}X-1=0 \ , (A=A^{\top})

equals the absolute values of the zeros of:

{\mathcal F}(Z)=\left| \begin{array}{ccc} A & B & C^{\top}/|C|\\ B^{\top} & -1 & Z-h/|C|\\ C/|C| & Z-h/|C| & 0 \end{array} \right| \ .

Here |C|=\sqrt{c_1^2+\dots+c_n^2} and it is assumed the surfaces do not intersect.

Ex

Example. Find the distance from the line 2\, x_1- x_2=0 to the ellipse 7\,x_1^2-4\,x_1x_2 + 6\, x_2^2-47\, x_1 -24\, x_2 +124 = 0.

Solution. Here

{\mathcal F}(Z)=\left| \begin{array}{ccc} A & B & C^{\top}/|C| \\ B^{\top} & -1 & Z-h/|C| \\ C/|C| & Z-h/|C| & 0 \end{array} \right| = \left| \begin{array}{cccc} -\frac{7}{124} & \frac{1}{62} & \frac{47}{248} & \frac{2}{\sqrt{5}} \\ &&& \\ \frac{1}{62} & - \frac{3}{62} & \frac{3}{31} &- \frac{1}{\sqrt{5}} \\ &&& \\ \frac{47}{248} & \frac{3}{31} & -1 & Z \\ &&& \\ \frac{2}{\sqrt{5}} & - \frac{1}{\sqrt{5}} & Z & 0 \end{array} \right| =
=-\frac{1}{307520}\left(760\,Z^2+1592\sqrt{5}\, Z+2383 \right)

and zeros of this polynomial are as follows:

-\frac{199}{190}\sqrt{5}\pm \frac{1}{76} \sqrt{13570} \ .

Result.

d = \left| -\frac{199}{190}\sqrt{5}+ \frac{1}{76} \sqrt{13570} \right| \approx 0.809219 \ .

Distance between quadrics

Th

Theorem.[4]. Let X^{\top} A_{1} X =1 and X^{\top} A_{2} X =1 be the quadrics in {\mathbb R}^{n} with the first one being an ellipsoid. These quadrics do not intersect iff the matrix A_1-A_{2} is sign definite.

Proof is HERE

Th

Theorem. [3]. Under the condition of the previous theorem, the square of the distance between the ellipsoid X^{\top} A_{1} X =1 and the quadric X^{\top} A_{2} X =1 equals the minimal positive zero of the polynomial

{\mathcal F}(z) = {\mathcal D}_{\lambda} (\det (\lambda A_1 + (z- \lambda) A_2 - \lambda (z-\lambda) A_1 A_2)),

provided that this zero is not a multiple one. Here {\mathcal D}_{} stands for the discriminant of the polynomial treated w.r.t. \lambda_{}.

Ex

Example. Find the distance between the ellipses

10\,x_1^2-12\,x_1x_2+8\,x_2^2=1 \qquad and \qquad x_1^2+x_1x_2+x_2^2=1 \ .

Solution. Here

A_1= \left( \begin{array}{rr} 10 & - 6 \\ -6 & 8 \end{array} \right), \quad A_2= \left( \begin{array}{rr} 1 & \frac{1}{2} \\ \frac{1}{2} & 1 \end{array} \right)

and the matrix A_1-A_2 is positive definite. Thus the ellipses do not intersect.

G(\lambda,z)=\det (\lambda A_1 + (z- \lambda) A_2 - \lambda (z-\lambda) A_1 A_2)=
=33\,\lambda^4+\left(-66z+\frac{149}{2}\right)\lambda^3+\left(33\,z^2-61\,z+\frac{83}{4}\right)\lambda^2+\left(-\frac{27}{2}z^2+\frac{45}{2}z\right)\lambda+\frac{3}{4}\,z^2

and the discriminant of this polynomial w.r.t. \lambda equals

{\mathcal F}(z)=\frac{3}{16}z^2 \times
\times ({\scriptstyle 936086976}\, z^6-{\scriptstyle 10969697376}\,z^5+ {\scriptstyle 50706209664}\, z^4 -{\scriptstyle 115515184664}\, z^3+{\scriptstyle 130176444432}\, z^2 -{\scriptstyle 59826725574}\,z+{\scriptstyle 2866271785}) \ .

Its positive roots are as follows:

z_1 \approx 0.053945666,\ z_2 \approx 1.3340583883,\ z_3 \approx 1.95921364,\ z_4 \approx 2.8785867381 \ .

Result. d= \sqrt{z_1} \approx 0.23226206.

§

For the general case, the degree of {\mathcal F}(z) from the last theorem (on excluding the extraneous factor z^{n(n-1)}) equals n(n+1).

To find the nearest points in the quadrics one can utilize the following algorithm:

1. If z=z_{\ast} is a zero of {\mathcal F}(z) then the polynomial

G(\lambda, z_{\ast}) = \det ( \lambda A_1 +(z_{\ast}-\lambda)A_2 - \lambda (z_{\ast}-\lambda) A_2A_1)

has a multiple zero \lambda = \lambda_{\ast}. Under the assumptions of the theorem, the multiplicity of this zero equals to 2, there is no other multiple zeros, and this zero can be expressed as a rational function of z_{\ast} via subdiscriminants.

2. The coordinates column X_{\ast} of the point in the first quadric satisfies the system of the linear homogeneous equations

( \lambda_{\ast} A_1 +(z_{\ast}-\lambda_{\ast})A_2 - \lambda_{\ast} (z_{\ast}-\lambda_{\ast}) A_2A_1) X = \mathbb O

with an infinite set of solutions (since its determinant vanishes). From the mentioned set we extract the solutions with the property X^{\top}A_1X=1.

Under the assumptions of the theorem, there exists precisely two such solutions (due to the symmetry of the problem, v. Fig.).

Similarly, the coordinate column Y_{\ast} of the point in the second quadric Y^{\top}A_2Y=1 is a solution of the system

( \lambda_{\ast} A_1 +(z_{\ast}-\lambda_{\ast})A_2 - \lambda_{\ast} (z_{\ast}-\lambda_{\ast}) A_1A_2) Y = \mathbb O \ .
§

Notice, that the matrices of the considered linear systems differ only by transposition.

To find the solution to the system of linear homogeneous equations, let us compose the solution column from the cofactors to the entries of any row of the matrix

M= \lambda_{\ast} A_1 +(z_{\ast}-\lambda_{\ast})A_2 - \lambda_{\ast} (z_{\ast}-\lambda_{\ast}) A_2A_1 \ .

Then X_{\ast} differs from this column only by the multiple which can be determined from the condition X^{\top}A_1X=1. In a similar way, to find the column Y_{\ast} let us compose it from the cofactors to the elements of any column of the same matrix M, and multiply it by a constant in order to provide the fulfilment of the condition Y^{\top}A_2Y=1.

3. The obtained pairs X_{\ast},Y_{\ast} should be adjusted by the restriction

(X_{\ast}-Y_{\ast})^{\top}(X_{\ast}-Y_{\ast})=z_{\ast} \ .
Ex

Example. Find the nearest points in the ellipses from the previous example.

Solution. For the obtained value z=z_{\ast}\approx 0.053945 the determinant of the matrix

M=\left( \begin{array}{cc} 7\,\lambda^2+(-7z+9)\lambda+z & -2\lambda^2+(2\,z-\frac{13}{2})\lambda+\frac{1}{2}z \\ & \\ -\lambda^2+(z-\frac{13}{2})\lambda+\frac{1}{2}z & 5\lambda^2+(-5z+7)\lambda+z \end{array} \right)

treated as a polynomial in \lambda, possesses a multiple zero. We find this zero1) via the subdiscriminant technique:

\lambda=-\frac{-725274\,z^5+1455894\,z^4+\frac{11286981}{2}z^3-\frac{26486523}{2}z^2+\frac{42000075}{8}z} {17591706\,z^4-109992894\,z^3+\frac{450450691}{2}z^2-\frac{315606253}{2}z+\frac{77466805}{8}} \ .

Substitution z=z_{\ast} yields one \lambda_{\ast} \approx -0.135760.

Furthemore, for the obtained values of z_{} and \lambda_{} the system of linear equations

MX=\mathbb O_{2\times 1}

treated with respect to the column X_{2\times 1} has an infinite number of solutions. One of these solutions can be found with the aid of the cofactors to the entries of, for instance, the second row of the matrix M_{}:

\left( \begin{array}{c} 2\lambda^2-(2\,z-\frac{13}{2})\lambda-\frac{1}{2}z \\ \\ 7\,\lambda^2+(-7z+9)\lambda+z \end{array} \right) \quad \begin{array}{c} \longrightarrow \\ z=z_{\ast}, \lambda= \lambda_{\ast} \end{array} \quad X\approx \left( \begin{array}{c} -0.857907 \\ \\ -0.987617 \end{array} \right) \ .

Any other solution can be obtained from this on multiplication by a constant (i.e. by «streching» of the vector). We utilize such an opportunity with the aim to provide the condition X^{\top}A_{1} X =1.

X_{\ast}=\frac{1}{\sqrt{X^{\top}A_1 X}} X \approx \left( \begin{array}{c} -0.3838312 \\ -0.4418639 \end{array} \right) \ .

Similarly, to find the point in the other ellipse, one should solve the system

M^{\top}Y=\mathbb O_{2\times 1} \ ,

with the aid of the cofactors to the second column of the matrix M_{}:

\left( \begin{array}{c} \lambda^2-(z-\frac{13}{2})\lambda-\frac{1}{2}z \\ \\ 7\,\lambda^2+(-7z+9)\lambda+z \end{array} \right) \quad \begin{array}{c} \longrightarrow \\ z=z_{\ast}, \lambda= \lambda_{\ast} \end{array} \quad \left( \begin{array}{c} -0.8836615 \\ \\ -0.9876166 \end{array} \right) \quad \Rightarrow \quad Y_{\ast} \approx \left( \begin{array}{c} -0.5449964 \\ \\ -0.6091105 \end{array} \right) \ .

Result. \approx \pm (0.383831,\, 0.441864) and \approx \pm (0.544996,\, 0.609110) respectively (with the correlated signs).

Check. Taking the + sign results in:

X_{\ast}-Y_{\ast} \approx \left( \begin{array}{c} -0.1611652 \\ -0.1672466 \end{array} \right)= \lambda_{\ast} A_1X_{\ast}=(\lambda_{\ast}-z_{\ast})A_2Y_{\ast},\quad (X_{\ast}-Y_{\ast})^{\top}(X_{\ast}-Y_{\ast})\approx \mathbf{0.0539456}4 \ .
Th

Theorem. Let X^{\top} A_{1}X+2\,B^{\top}_1X-1=0 and X^{\top} A_{2}X+2B^{\top}_2X-1=0 be quadrics in {\mathbb R}^{n}, with the first one being an ellipsoid. These quadrics intersect iff the polynomial

\Phi (z) = {\mathcal D}_\lambda \left( \det \left( \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1-z \end{array} \right] - \lambda \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] \right) \right)

possesses zeros of distinct signs, or \Phi (0)=0. Here {\mathcal D} is the discriminant of the polynomial treated w.r.t. \lambda_{}.

=>

For the existence of the tangency point for X^{\top} A_1X+2\,B^{\top}_1X-1=0 and X^{\top} A_2X+2B^{\top}_2X-1=0 it is necessary and sufficient that

{\mathcal D}_\lambda \left( \det \left( \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \lambda \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] \right) \right) =0 \ .

Th

Theorem. [3]. If the condition of the previous theorem is not fulfilled then the square of the distance between the ellipsoid X^{\top} A_{1}X+2\,B^{\top}_1X-1=0 and the quadric X^{\top} A_{2}X+2B^{\top}_2X-1=0 equals the minimal positive zero of the polynomial

{\mathcal F}(z) = {\mathcal D}_{\mu_1, \mu_2} \left( \det \left( \mu_1 \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] + \mu_2 \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \left[ \begin{array}{cc} A_2 A_1 & A_2 B_1\\ B_2^{\top} A_1 & B_2^{\top}B_1 - \mu_1 \mu_2 z \end{array} \right] \right) \right),

provided that this zero is simple. Here {\mathcal D}_{} is the discriminant of the polynomial treated w.r.t. \mu_1, \mu_{2}.

Ex

Example. Find the distance between the ellipses

-\frac{1}{2}\,x_1^2+\frac{1}{2}\,x_1x_2-\frac{3}{2}\,x_2^2+\frac{5}{2}\,x_1+4\,x_2=1 \qquad and \qquad -\frac{1}{84}\,x_1^2-\frac{4}{189}\,x_2^2-\frac{1}{3}\, x_1=1 \ .

Solution. Here

A_1= \left( \begin{array}{rr} -\frac{1}{2} & \frac{1}{4} \\ \\ \frac{1}{4} & -\frac{3}{2} \end{array} \right), \quad B_1=\left( \begin{array}{c} \frac{5}{4} \\ \\ 2 \end{array} \right), \quad A_2= \left( \begin{array}{cc} -\frac{1}{84} & 0 \\ \\ 0 & -\frac{4}{189} \end{array} \right),\quad B_2=\left( \begin{array}{r} -\frac{1}{6} \\ \\ 0 \end{array} \right) \ .

Let us verify first the conditions of intersection of the manifolds. The polynomial

\Phi (z) = {\mathcal D}_\lambda \left(-\begin{array}{c} \frac{157}{32} \end{array} \lambda^3-\left\{ \begin{array}{c} \frac{4315}{3024} \end{array} + \begin{array}{c} \frac{11}{16}z \end{array} \right\}\lambda^2+\left\{-\begin{array}{c} \frac{11}{2646} \end{array} + \begin{array}{c} \frac{43}{1512} \end{array} z \right\}\lambda- \begin{array}{c} \frac{1}{3969}\end{array} z + \begin{array}{c} \frac{4}{11907} \end{array}\right)=
=\begin{array}{c}\frac{1}{{\scriptstyle 9219465541730304}} \end{array} ({\scriptstyle 505118694465}\,z^4-{\scriptstyle 1023679248858}\,z^3- {\scriptstyle 7568287236783}\,z^2+ {\scriptstyle 33720131260536}\,z +{\scriptstyle 34005894083152})\ .

possesses precisely two real zeros, both are negative. Ellipses do not intersect. Furthemore,

\Psi(\mu_1,\mu_2,z)=\det \left( \mu_1 \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] + \mu_2 \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \left[ \begin{array}{cc} A_2 A_1 & A_2 B_1\\ B_2^{\top} A_1 & B_2^{\top}B_1 - \mu_1 \mu_2 z \end{array} \right] \right) =
=\frac{11}{16}z\mu_1^3 \mu_2+\frac{43}{1512}z\mu_1^2\mu_2^2+\frac{1}{3969}z\mu_1\mu_2^3+ \frac{157}{32}\mu_1^3-\frac{4315}{3024}\mu_1^2\mu_2+
+\frac{275}{12096}z\mu_1^2\mu_2+\frac{11}{2646}\mu_1\mu_2^2+\frac{2}{3969}z\mu_1\mu_2^2+\frac{4}{11907}\mu_2^3+\frac{3925}{24192}\mu_1^2+
+\frac{11}{63504}z\mu_1\mu_2-\frac{619}{31752}\mu_1\mu_2+\frac{8}{11907}\mu_2^2+\frac{157}{127008}\mu_1+\frac{11}{47628}\mu_2 \ .

Calculate the discriminant of this polynomial w.r.t. \mu_{1} and \mu_{2} via representation of the corresponding resultant

{\mathcal R}_{\mu_1,\mu_2}\left(\frac{\partial \Psi}{\partial \mu_1}, \frac{\partial \Psi}{\partial \mu_2}, \Psi \right)

as the Bézout determinant [5]:

\mathfrak B= \left( \begin{array}{cccc} -{\scriptstyle 949850}\,z-{\scriptstyle 38319304} & -{\scriptstyle 76994841}\,z+ {\scriptstyle 29798905836} & \dots & \\ {\scriptstyle 179712037934}\,z^2-{\scriptstyle 6628863332080}\,z-{\scriptstyle 18668859390944800} & & \dots & \\ \dots &&& \dots \\ & & & \end{array} \right)

The expressions for the entries of the first and the last rows are HERE.

{\mathcal F}(z) =\det (\mathfrak B) \equiv 3869893(20090\,z+3526681)^2 \times
\times ({\scriptstyle 12866891832025}\,z^{12}-{\scriptstyle 2445505463588880}\,z^{11}-{\scriptstyle 10867111637549652716}\,z^{10}-{\scriptstyle 3123865087697933253136}\,z^9+
+{\scriptstyle 1561852119815441835822424}\,z^8+{\scriptstyle 1041845279230362476059640640}\,z^7+{\scriptstyle 302844249329911871856294474624}\,z^6+
+{\scriptstyle 50781476668832773753935668661952}\,z^5+{\scriptstyle 2215513880036430404751762329796624}\,z^4-
-{\scriptstyle 646131957386364232922218724008039168}\,z^3-{\scriptstyle 99189074464451279399168578577559865856}\,z^2-
-{\scriptstyle 5789019527920299026625801973715386789888}\,z+{\scriptstyle 60730952901233749068462660878127980941312})

The first factor in z_{} is an extraneous one and should be reduced. Positive zeros of the second factor are:

z_1 \approx 9.018398, \ z_2 \approx 121.596733,\ z_3 \approx 582.358405,\ z_4 \approx 1031.421186 \ .

Result. d = \sqrt{z_1} \approx 3.003065_{}.

The coordinates of the nearest points in the quadrics can be found by the following algorithm:

  • On evaluating the minimal positive zero z_{\ast} of {\mathcal F}(z) one can establish the corresponding values of \mu_{1} and \mu_{2}. This correspondence has the meaning that for z=z_{\ast} the discriminant of the polynomial
\Psi(\mu_1,\mu_2,z)=\det \left( \mu_1 \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] + \mu_2 \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \left[ \begin{array}{cc} A_2 A_1 & A_2 B_1\\ B_2^{\top} A_1 & B_2^{\top}B_1 - \mu_1 \mu_2 z \end{array} \right] \right)

treated w.r.t \mu_1,\mu_2 vanishes. That means the polynomial possesses a multiple zero which we denote (\mu_{1\ast},\mu_{2\ast}). This zero can be represented as a rational function of z_{\ast} with the aid of the minors of the Bézout matrix. Let, for instance, the matrix \mathfrak B of the order N_{} be constructed for the monomial basis with the first three power product equal to 1,\mu_{1}, \mu_2. Denote by {\mathfrak B}_{N1}, {\mathfrak B}_{N2}, {\mathfrak B}_{N3} the cofactors to the entries of the last row of this matrix. One has then

\mu_{1\ast} = \frac{\mathfrak B_{N2}}{\mathfrak B_{N1}};\ \mu_{2\ast} = \frac{\mathfrak B_{N3}}{\mathfrak B_{N1}} \ .
  • Compose the matrix
M= \mu_{1\ast} A_1+\mu_{2\ast}A_2-A_2A_1 \ .

Then the coordinates columns of the nearest points in the quadrics can be found via the formulas:

X_{\ast}=M^{-1} (A_2B_1-\mu_{1\ast} B_1-\mu_{2\ast}B_2),\ Y_{\ast}=(M^{-1})^{^{\top}} (A_1B_2 - \mu_{1\ast} B_1-\mu_{2\ast}B_2).
Ex

Example. Find the nearest points in the ellipses from the previous example.

Solution. Substitute the value of the square of the distance z=z_{\ast} into the formulas for the multiple zero evaluation:

\mu_1=\frac{\mathfrak B_{9,2}}{\mathfrak B_{9,1}}\equiv -\frac{2}{21} \frac{p_2(z)}{p_1(z)},\ \mu_2=\frac{\mathfrak B_{9,3}}{\mathfrak B_{9,1}}\equiv -\frac{1099}{8} \frac{p_3(z)}{p_1(z)}

with

p_1(z)={\scriptstyle 30581063813712982235616866861258531260075854083860480}+\dots +{\scriptstyle 42267948346218643456100}\,z^{13} \ ,
p_2(z)={\scriptstyle 6423295122838229007549546733287643446036432415004672}+\dots + {\scriptstyle 10295520700745795900000}\,z^{13}

and

p_3(z)={\scriptstyle 11528328181753695140063436659475618124233172074496}+\dots +{\scriptstyle 303317089743521700}\,z^{13} \ .

(Complete expressions are HERE.) The result is as follows:

\mu_{1\ast}\approx 0.042093 ,\ \mu_{2\ast}\approx 0.593211 \ .

Then the matrix M_{} equals:

M=\mu_{1\ast} A_1+\mu_{2\ast}A_2-A_2A_1= \left(\begin{array}{rr} -0.034061 & 0.013499 \\ 0.015814 & -0.107441 \end{array} \right)

and using the above formulas for the coordinates columns one arrives at the

Result.

X_{\ast}\approx \left(\begin{array}{r} -0.482471 \\ 1.106514 \end{array} \right),\ Y_{\ast}\approx \left( \begin{array}{r} -3.462629\\ 0.736308 \end{array} \right)\ .

Check.

(X_{\ast}-Y_{\ast})^{\top}(X_{\ast}-Y_{\ast})\approx \mathbf{9.018398280}3\ ,
X_{\ast}^{\top}A_1X_{\ast}+2B_1^{\top}X_{\ast}-1 \approx 1\cdot 10^{-9}\ , \ Y_{\ast}^{\top}A_2Y_{\ast}+2B_2^{\top}Y_{\ast}-1\approx -3\cdot 10^{-10}\ ,

and the vector X_{\ast}-Y_{\ast} is normal to both ellipses in the corresponding points:

A_1X_{\ast}+B_1= \left(\begin{array}{r} 1.767863990 \\ 0.219610712 \end{array} \right)=\mu_{2\ast} (X_{\ast}-Y_{\ast}), \ A_2Y_{\ast}+B_2= \left(\begin{array}{r} -0.1254448880 \\ -0.0155832356 \end{array} \right)=-\mu_{1\ast} (X_{\ast}-Y_{\ast}) \ .
§

For the general case, the degree of {\mathcal F}(z) from the last theorem (on excluding the extraneous factor) equals 2n(n+1). Its coefficients might be huge:

Ex

Example. Find the distance between ellipsoids

7\,x_1^2+6\,x_2^2+5\,x_3^2-4\,x_1x_2-4\,x_2x_3-37\,x_1-12\,x_2+3\,x_3+54=0

and

189\,x_1^2+x_2^2+189\,x_3^2+2\,x_1x_3-x_2x_3-27=0\ .

Solution. Here

\mathcal F (z)= \underbrace{\scriptstyle 891807829233048602 \dots 129270962946048}_{146\ digits} \, z^{24} + \dots + \underbrace{{\scriptstyle 11195843896426573542 \dots 420939042193186989409}}_{189\ digits}

Result. d \approx \sqrt{1.3537785005} \approx 1.1635198754_{}.

General algebraic curves and manifolds

Distance from a point to a planar agebraic curve

Problem. Let an algebraic curve be defined by the equation

\Phi(x,y)=0 \ .

Here \Phi_{}(x,y) is a polynomial in x_{} and y_{} with real coefficients. Evaluate the distance to this curve from the origin.

For this problem, some extra obstacle appeared which has not caused much difficulty for the quadrics, nemely the problem of existence of solution. It might happened that the given equation does not define any real curve in the plane.

We start the treatment of the stated problem with a particular case of a polynomial: let it be even one w.r.t. y_{}. Geometrical meaning of this condition is the symmetry of the curve (if it exists) w.r.t. the axis \mathbb Ox. Analytically such a polynomial can be represented in the form of a polynomial in y^2:

F(x,Y) \equiv \Phi_{}(x,y) \quad for \quad Y=y^2 \ .
Th

Theorem 1 [7]. Let \Phi_{}(x,y) \equiv \Phi_{}(x,-y). Equation \Phi_{}(x,y)=0 does not possess real solutions if the following conditions are satisfied:

(a) Equation \Phi(x,0)=0 does not possess real solutions;

(b) Equation

\mathcal F(z)=\mathcal D_x( F(x,z-x^2))=0

does not possess positive solutions.

If any of these conditions fails then the distance from X_0=[0,0] to the curve \Phi(x_{},y)=0 equals either the minimal absolute value of real zeros of the equation \Phi(x,0)=0 or the square root from the minimal positive zero of the equation \mathcal F(z)= 0 provided that this zero is not a multiple one.

Ex

Example. Evaluate the distance from the origin to the curve

\Phi(x,y)=x^6-5\,x^4y^2-y^6-6\,x^5+6\,xy^4+10\,y^4+25\,x-45=0 \ .

Solution. Equation

\Phi(x,0)=x^6-6\,x^5+25\,x-45=0

has the real zeros \mu_1\approx -1.621919 and \mu_2 \approx 5.986387. Furthemore, one has

F(x,Y)=x^6-5\,x^4Y-Y^3-6\,x^5+6\,xY^2+10\,Y^2+25\,x-45

and

\mathcal F(z)=\mathcal D_x (F(x,z-x^2))= {\scriptstyle 124422592}\,z^{15}-{\scriptstyle 1996675968}z^{14}-{\scriptstyle 26107738048}\,z^{13}+{\scriptstyle 270691240064}\,z^{12}+ {\scriptstyle 1462429768576}z^{11}
-{\scriptstyle 31070151855680}z^{10}+ {\scriptstyle 104850679100160}\,z^9+{\scriptstyle 106422502370800}\,z^8-{\scriptstyle 1956603249193600}\,z^7+{\scriptstyle 1683409252901600}\,z^6
+{\scriptstyle 3565828983027500}z^5 -{\scriptstyle 23058839076745500}\,z^4+{\scriptstyle 30272455856370000}\,z^3+{\scriptstyle 28139412928130000}\,z^2-{\scriptstyle 97452805338000000}\, z
+{\scriptstyle 171049864407603125}

has a minimal positive zero equal to \lambda \approx 1.965293. Since \sqrt{\lambda} < |\mu_1|, we arrive at the following

Answer. d \approx 1.334155.

It is evident how to tackle the problem if the polynomial \Phi_{}(x,y) is an even one w.r.t. x_{}. How to deal with the case of a polynomial which is not even in any of its variables? — Let us evenize it. Consider the polynomial

\tilde F(x,Y) \equiv \Phi_{}(x,y) \Phi_{}(x,-y) \quad for \quad Y=y^2 \ .
Th

Theorem 2 [7]. Equation \Phi_{}(x,y)=0 does not possess real solutions if the following conditions are satisfied:

(a) equation \Phi(x,0)=0 does not possess real solutions;

(b) equation

\tilde \mathcal F(z)=\mathcal D_x( \tilde F(x,z-x^2))=0

does not possess positive solutions.

If any of these conditions fails then the distance from X_0=[0,0] to the curve \Phi(x_{},y)=0 equals either the minimal absolute value of real zeros of the equation \Phi(x,0)=0 or the square root from the minimal positive zero of the equation \mathcal F(z)= 0 provided that this zero is not a multiple one.

Ex

Example. Evaluate the distance from the origin to the curve

\begin{array}{lll} \Phi(x,y) & = & 32\,x^4y+64\,x^2y^3+32\,y^5-16\,x^4-96\,x^2y^2-80\,y^4+ \\ && +48\,x^2y+80\,y^3+120\,x^2-576\,xy+56\,y^2+160\,x-118\,y+71=0 \ . \end{array}

Solution. Skipping the intermediate computations we present here just only the final expression for the discriminant:

\tilde \mathcal F(z) \equiv \tilde \mathcal F_1(z) \tilde \mathcal F_2^2(z)

where

\tilde \mathcal F_1(z) = {\scriptstyle 87241523200}\,z^{15}-{\scriptstyle 244343373824}\,z^{14}+ {\scriptstyle 6135125901312}\,z^{13}-{\scriptstyle 99762334334976}\,z^{12}+{\scriptstyle 122650759266304}\,z^{11}-
-{\scriptstyle 2018722496380928}\,z^{10} +{\scriptstyle 36775841922285568}\,z^9+{\scriptstyle 83476886207856640}\,z^8-{\scriptstyle 125448251244072960}\,z^7-{\scriptstyle 3659244138715855872}\,z^6
-{\scriptstyle 16653164114254566912}\,z^5-{\scriptstyle 39789124482714260608}\,z^4+{\scriptstyle 21724179049244829584}\,z^3-{\scriptstyle 2250891598084946580}\,z^2+{\scriptstyle 484733011031273132}\,z
-{\scriptstyle117947376101831257}

and

\tilde \mathcal F_2(z) =4096\,z^6+18432\,z^5+18176\,z^4-1501440\,z^3+305136\,z^2+2195912\,z+709721 \, .

Polynomial \tilde \mathcal F_1(z) has three real zeros: \lambda_1 \approx 0.208349,\ \lambda_2 \approx 0.360823,\ \lambda_3 \approx 6.480707. Polynomial \Phi(x,0) has two real zeros: \mu_1 \approx -1.835484, \mu_2 \approx 3.306151.

The factor \tilde \mathcal F_2^2(z) is ignored as an extraneous one, i.e. the values of its zeros (all of them are multiple) are not compared with \lambda_1 and \mu_1^2. Where this multiple appeares from? — To guess its origin, let us evaluate its positive zeros: \xi_1 \approx 1.483677, \xi_2 \approx 5.553837. Draw now the circumferences \{x^2+y^2= \xi_{j}\}_{j=1,2} in the last figure:

Circumferences pass through the points of intersection of the curves \Phi_{}(x,y) = 0 and \Phi_{}(x,-y) =0.

Hypothesis. Expand \Phi_{}(x,y) in powers of y_{} and split it in even and odd terms w.r.t. this variable:

\Phi_{}(x,y) \equiv F_1(x,Y)+ y F_2(x,Y) \qquad for \quad Y=y^2 \ .

The following identity is valid up to a constant factor

\tilde \mathcal F_2(z) \equiv \mathcal R_x(F_1(x,z-x^2),F_2(x,z-x^2)) \ .

Here \mathcal R_{} stands for the resultant of the polynomials treated w.r.t. x_{}.

Answer. d \approx 0.456453.

Miscellanea

Generalized Fermat-Torricelli problem

Problem. Given the coordinates of three noncollinear points P_1=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3) in the plane, find the coordinates of the point P_{\ast}=(x_{\ast},y_{\ast}) which gives a solution for the optimization problem

\min_{(x,y)} F(x,y) \quad for \quad F(x,y)= \sum_{j=1}^3m_j \sqrt{(x-x_j)^2+(y-y_j)^2} \ .

Here m_1,m_2,m_3 are usually assumed to be real positive numbers.

The stated problem in its particular case of equal values m_1=m_2=m_3=1 is known since 1643 as the (classical) Fermat-Torricelli problem. Generalization of the problem to the general case (of not necessarily equal m_1,m_2,m_3) was investigated since the XIX century. This generalization is known under different names: the Steiner problem, the Weber problem, the problem of railway junction2), the three factory problem. The two last names were inspired by the facility location problem like the following one. Let the cities P_1,P_2, and P_3 be the sources of iron ore, coal, and water respectively. To produce one ton of steel, the steel works need m_1 tons of iron, m_2 tons of coal and m_3 tons of water. Assuming that the freight charge for a ton-kilometer is independent of the nature of the cargo, find the optimal position for the steel works connected with P_1,P_{2}, and P_{3} via straight roads so as to minimize the transportation costs.

§

The detailed discussion of this problem is HERE.


Problems

are HERE

References

[1]. Cesàro E. Algebraic Analysis and Infinitesimal Calculus.

[2]. Ikramov H.D. Linear algebra: problems book. Мir. Moscow. 1983

[3]. Uteshev A.Yu., Yashina M.V. Distance Computation from an Ellipsoid to a Linear or a Quadric Surface in {\mathbb R}^n. Lect.Notes Comput. Sci. 2007. V.4770. P.392-401

[4]. Uteshev A.Yu., Yashina M.V. Metric Problems for Quadrics in Multidimensional Space. J.Symbolic Computation, 2015, Vol. 68, Part I, P. 287-315.

[5]. Proskuryakov, I.V. Problems in Linear Algebra. Mir. Moscow. 1978

[6]. Bikker P.,Uteshev A.Yu. On the Bézout Construction of the Resultant. J.Symbolic Computation, 1999, Vol.28, № 1. P.45-88

[7]. Uteshev A.Yu., Goncharova M.V. Metric problems for algebraic manifolds: Analytical approach. Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), 2017, IEEE, http://ieeexplore.ieee.org/document/7974027/

1) In a manner similar to the one treated in this Section
2) (Germ.) Problem des Knotenpunktes

2018/02/24 12:30 редактировал au