§

Satellite page for ☞ Distance evaluation between geometric objects

⊗

The page is under reconstruction; repair works: 15.01.2015 — ??.??.????

—-

We discuss here the consequences in $ \mathbb R^{3} $ of the general result on the distance evaluation from a point to a quadric in $ {\mathbb R}^{n} $. The main task here is to detalize the algorithms for computation of the distance equation and for finding the nearest (and the farthest) point coordinates in the ellipse or ellipsoid.

§

The results below (if not specially noted) are contained in [1,2].

Тh

**Theorem 1.** *The square of the distance to the ellipse*

$$ a_{11}x^2+2\,a_{12}xy+a_{22}y^2+2\, b_1 x + 2\, b_2 y -1 =0 $$
*from the point* $ (x_{0},y_0) $ * not lying in the ellipse,
equals the minimal positive zero of * **the distance equation**
$$
{\mathcal F}(z)={\mathcal D}_{\mu}(\Phi(\mu,z))=0
$$
*provided that this zero is not a multiple one.
Here*
$$
\Phi(\mu,z)=
\left| \begin{array}{ccc}
a_{11}-\mu & a_{12} & b_1+\mu x_0 \\
a_{12} & a_{22}-\mu & b_{2}+\mu y_0 \\
b_1+\mu x_0 & b_2+\mu y_0 & -1 + \mu (z-x_0^2-y_0^2)
\end{array}
\right| \ ,
$$
*and*
$ {\mathcal D}_{} $ *stands for the discriminant of the polynomial* $ \Phi(\mu,z) $ *considered w.r.t. the variable* $ \mu_{} $, *(whereas the remained variables are treated as parameters).*

Ex

**Example.** Find the distance from the point $ (2,1) $ to the ellipse

$$ -\frac{1}{2}x^2+\frac{1}{2}xy-\frac{3}{2}y^2+\frac{5}{2}x+4\,y-1=0 \ . $$

**Solution.** One has:
$$
\Phi(\mu,z)=\left| \begin{array}{ccc}
-1/2-\mu & 1/4 & 5/4+ 2\,\mu \\
1/4 & -3/2-\mu & 2+\mu \\
5/4+ 2\,\mu & 2+\mu & -1 + \mu (z-5)
\end{array}
\right|=
$$
$$
=z\mu^3+\left(2\,z+\frac{11}{2}\right)\mu^2+\left(\frac{11}{16}z+\frac{49}{4}\right)\mu+\frac{157}{32} \ .
$$
The discriminant of a cubic polynomial can be calculated by the formula
$$
{\mathcal D}_{\mu}(A_0\mu^3+A_1\mu^2+A_2\mu+A_3)=
$$
$$
=A_1^2A_2^2-4\,A_1^3A_3-4\,A_0A_2^3+18\,A_0A_1A_2A_3-27\,A_0^2A_3^2 \ .
$$
All the zeros of the polynomial
$$
{\mathcal F}(z)={\mathcal D}_{\mu}(\Phi(\mu,z))\equiv 2^{-10} \left(605\,z^4-27932\,z^3+306696\,z^2-1181744\,z+1304864 \right)
$$
are real
$$ z_1 \approx 1.845415, \ z_2 \approx 5.717733\ , \ z_3 \approx 6.333919,\ z_4 \approx 32.271528 \ . $$
Thus the distance from the given point to the given ellipse equals $ \sqrt{z_1} \approx 1.358460 $.
♦

It is possible to write down an explicit expression for the distance equation as a function of the parameters of the problem (i.e. the coefficients of the ellipse equation and coordinates of the point), and I present it here for the case where the ellipse equation is reduced to the canonical form. The next result is obtained from Theorem $ 1 $ with the aid of substitution $ \mu \rightarrow 1/\mu $.

Тh

**Theorem 2.** *The square of the distance to the ellipse*

$$ \frac{x^2}{a^2}+\frac{y^2}{b^2}=1 $$
*from the point* $ (x_{0},y_0) $ * not lying in the ellipse,
equals the minimal positive zero of * **the distance equation**
$$
{\mathcal F}(z)={\mathcal D}_{\mu}(\Phi(\mu,z))=0
$$
*provided that this zero is not a multiple one.
Here*
$$
\Phi(\mu,z)=\mu^3+A_1\mu^2+A_2\mu+A_3 =
$$
$$
=\mu^3-\left\{a^2+b^2-x_0^2-y_0^2+z \right\}\mu^2 +
\left\{-a^2b^2\left(\frac{x_0^2}{a^2}+\frac{y_0^2}{b^2} -1 \right)+z(a^2+b^2) \right\}\mu -
a^2b^2z \ ,
$$
*and*
$ {\mathcal D}_{} $ *stands for the discriminant of the polynomial* $ \Phi(\mu,z) $ *considered w.r.t. the variable* $ \mu_{} $, *(whereas the remained variables are treated as parameters).*

Computation of the discriminant for the cubic polynomial is performed via the above mentioned formula:
$$
{\mathcal D}_{\mu}(\mu^3+A_1\mu^2+A_2\mu+A_3)=
$$
$$
=A_1^2A_2^2-4\,A_1^3A_3-4\,A_2^3+18\,A_1A_2A_3-27\,A_3^2 \ ,
$$
however further expansion into powers of $ z_{} $ becomes rather cumbersome. With the complete expansion presented
☞
HERE, we now restrict ourselves only by writing down its leading and constant term^{1)}:
$$
\mathcal F(z)=
(a^2-b^2)^2 z^4+\dots +
$$
$$
+ a^{4}b^{4}G^2(x_0,y_0) \left[(x_0^2+y_0^2-a^2-b^2)^2+4\,a^2b^2G(x_0,y_0)\right] \, ;
$$
here $ G(x_0,y_0)= x_0^2/a^2+y_0^2/b^2-1 $.

If one replaces the expression «minimal positive zero for the distance equation» by «maximal positive…» one gets a solution of an optimization problem for finding the distance from $ (x_{0},y_{0}) $ to the farthest point in the ellipse. Hereinafter, the main results will be formulated in the version «minimal distance», while the examples will be presented for both problems.

If $ a\ne b $ (the ellipse is not a circle), the degree of the distance equation equals $ 4_{} $ and it can be resolved (at least, in theory) in radicals. Among its real zeros are the values of squares of two distances: from $ (x_{0},y_0) $ to the nearest and to the farthest point of the ellipse.

For finding the coordinates of the nearest point we will utilize the general result from the section ☞ DISTANCE BETWEEN QUADRICS. If $ z_{}=z_{\ast} $ stands for a real zero of the distance equation then the polynomial $ \Phi(\mu,z_{\ast}) $ posesses a multiple zero $ \mu=\mu_{\ast} $. Under the condition of the theorem, the multiplicity of this zero equals $ 2_{} $ (and there are no other multiple zeros for $ \Phi(\mu,z_{\ast}) $). The value for $ \mu_{\ast}^{} $ can be expressed as a rational function of the coefficients of this polynomial with the aid of, for instance, the result presented ☞ HERE: $$ \mu_{\ast}=\frac{9\,A_3-A_1A_2}{2(A_1^2-3\,A_2)} \ ; $$ here the values for $ A_1,A_2,A_3 $ are taken from Theorem 2 with substitution $ z_{}=z_{\ast} $ made into these expressions. The coordinates of the point in ellipse lying at the distance $ \sqrt{z_{\ast}} $ from $ (x_{0},y_0) $ are determined by the formulas $$ x_{\ast}=\frac{a^2x_0}{a^2-\mu_{\ast}},\quad y_{\ast}=\frac{b^2y_0}{b^2-\mu_{\ast}} \ . $$

Ex

**Example.** Find the distance from the point $ (3,4) $ to the nearest and the farthest point in the ellipse $ x^{2}/4+y^{2}=1 $.

**Solution.** For this example one has:
$$A_1=-z+20,\ A_2=5\,z-69,\ A_3=-4\, z \ . $$
The real zeros of the polynomial
$$ {\mathcal F}(z)= 9\,z^4-870\,z^3+31261\,z^2-524740\,z+3218436 $$
might be only positive (due to the Descartes rule of signs), one can establish that the number of these zeros equals $ 2_{} $:
$$ z_1 \approx 13.356826, \ z_2 \approx 42.721212\ . $$
Therefore the distance from the point to the ellipse equals $ \sqrt{z_1} \approx 3.654699 $ while the distance to the farthest point of the ellipse equals $ \sqrt{z_2} \approx 6.536146 $.

Let us now evaluate the coordinates of the nearest and the farthest point in the ellipse. For both of the found values $ z_{j} $ compute the values $$ \mu_{j}=\frac{9\,A_3-A_1A_2}{2(A_1^2-3\,A_2)}=\frac{5\,(z_j^2-41\,z_j+276)}{2\,(z_j^2-55\,z_j+607)} \ ; $$ one gets: $$ \mu_1 \approx -4.589712,\quad \mu_2 \approx 10.600200 \ . $$ Substitute these into the formulas for coordinates: $$ x_{j}=\frac{12}{4-\mu_{j}},\quad y_{j}=\frac{4}{1-\mu_{j}} \ . $$ Thus the nearest to $ (3,4) $ point in the ellipse has the coordinates $$ \approx ( 1.397020, 0.715600) , $$ while the farthest — $$ \approx (-1.818127, -0.416658) \ . $$ ♦

While treating the examples of the previous section, we are faced with the two different possibilities for the distance equation: the number of real zeros of the 4th order equation equals either $ 2 $ or $ 4 $, excluding the highly improbable case of existence of multiple zeros. Let us now determine the border in the border in the $ (x_0,y_0) $ plane between these two situations. The semiaxes $ a_{} $ and $ b_{} $ of the ellipse are specialized.

Analysis of the number of real zeros for the polynomial $ \mathcal F_{}(z) $ is carried out with the aid of the sign of its discriminant $$ \Psi(x_0,y_0)= \mathcal D_z ( \mathcal F(z)) $$ $$ \equiv 256\,a^2b^2(a^2-b^2)^2x_0^2y_0^2\left[\left\{(a^2-b^2)^2-a^2x_0^2-b^2y_0^2\right\}^3-27\,(a^2-b^2)^2a^2b^2x_0^2y_0^2\right]^3 \ . $$ For a specializations of parameters $ a_{} $ and $ b_{} $, the discriminant curve $ \Psi(x_{0},y_0)= 0 $ defines in $ (x_{0},y_0) $-plane the boundary for the domains with different numbers of real zeros for the corresponding distance equations. Let us clarify the geometry of this curve.

Ex

**Example.** Draw the curve $ \Psi(x_0,y_0) = 0 $ for the ellipse $ x^2/4+y^2=1 $.

**Solution.** In the $ (x,y_{}) $ plane the curve $ \Psi(x_0,y_{0})= 0 $ consists of three branches: the coordinate axes and the curve implicitly defined by the equation
$$
(4\,x_0^2+y_0^2-9)^3 +972\,x_0^2y_0^2=0 \, .
$$
In the figure below it is plotted in red.
This curve is known as **astroid** and it was first treated by Apollonius of Perga in 3rd century BC.
Apollonius came to this problem from the following considerations: find the number of normals which can be drawn through a point in the plane to a given conic section.
The problem can be solved in different ways, for instance astroid can be obtained as the evolute of the ellipse. The evolute can be represented either implicitly
$$ (2\,x)^{2/3}+y^{2/3}=3^{2/3} \ , $$
or in parametric form
$$
x=3/2 \cos^3(t),y=3\sin^3(t) \quad npu \quad t\in [0, 2\pi] \ .
$$

For the points $ (x_{0},y_0) $ internal to astroid, the distance equation $ {\mathcal F}(z)_{}=0 $ possesses $ 4 $ real zeros, while for the points outside the astroid there are $ 2 $ zeros. ♦

Let us go further in the analysis of the example aiming to answer the question: Why the assumption of simplicity of the minimal positive zero of $ {\mathcal F}(z)_{} $ is essential for the claims of Theorems $ 1 $ and $ 2 $ of the previous section?

Ex

**Example.** Draw the plot of the squared distance from the points in the $ x $-axis to the ellipse from the previous example
and determine the coordinates of the corresponding nearest points.

**Solution.** For $ y_{0}=0 $ the polynomial $ {\mathcal F}(z)_{} $ is factorizable into linear factors:
$$
{\mathcal F}(z) \equiv (z-(x_0-2)^2)(z-(x_0+2)^2)(3\,z - (3-x_0^2))^2 \ .
$$
Draw the plot of zero $ z_{1}=(x_0-2)^2 $in green while that of $ z_{2} = 1- x_0^2/3 $ in blue:

For the whole interval $ x_0\in [ 0, \sqrt{3}] $ of its positivity, the zero $ z_{2} $ is a minimal one for the polynomial $ {\mathcal F}(z) $. Nevertheless, for $ x_{0} > 3/2 $, the value of squared distance equals $ z_{1} $ and the distance plot happens to consist from two parts with the gluing point at $ (3/2, 1/4_{}) $.

To understand the reason of this occasion, let us determine the nearest to $ (x_{0},0) $ points in the ellipse. For $ x_{0} = 0 $ one gets two points $ x=0_{}, y=\pm 1 $. While $ x_{0} $ continuosely increases, the pair of the nearest points in the ellipse moves in the similar direction until reaching the points $$ x=4/3 x_0,\ y= \pm \sqrt{1-4/9x_0^2} \, . $$ Here $ y_{} $ is real only where $ x_{0}\le 3/2 $. What happens when $ x_{0} $ increases further? — The nearest to $ (x_{0},0) $ point in the ellipse becomes $ (2,0_{}) $ and it remains the nearest point for any locus of $ (x_{0},0) $. ♦

It may happen that the minimal positive zero of the polynomial $ {\mathcal F}(z)_{} $ is a multiple one generated by a pair of *imaginary* points in the ellipse. Although this case might seems to be a very improbable one, it needs to be controlled. For instance, it might be controlled via verification of the more robust condition, namely that the polynomial $ {\mathcal F}(z)_{} $ has not multiple zeros at all, i.e. its discriminant $ \mathcal D_{z} ({\mathcal F}(z)) $ is non-zero.

Consider an ellipse in the plane and draw the normal to it in any of its point $ A_{} $. Choose the points at a distance
$ h_{} $ from $ A_{} $. The set of the obtained points forms two curves known as the **equidistants** (or equidistant curves or offset curves) **to the ellipse**

Th

**Theorem 3.** *For the ellipse given parametrically by the equations*

$$ x= a\,\cos t,\ y= b\,\sin t \quad for \ t \in [0, 2\, \pi] , $$
*the equations for its equidistants are as follows*:
$$
x=\left(a\pm \frac{bh}{\sqrt{a^2 \sin^2 t+b^2 \cos^2 t}} \right)\cos \, t,\quad
y=\left(b\pm \frac{ah}{\sqrt{a^2 \sin^2 t+b^2 \cos^2 t}} \right)\sin \, t \quad for \ t \in [0,2\pi] .
$$
*The signs should be coordinated*.

Ex

**Example.** For the ellipse $ x^{2}/4+y^2=1 $, its equidistants corresponding to $ h_{}=1/2 $ and $ h_{}=3/4 $ are drawn in the figure.

With $ h_{} $ increasing from zero, for some specializations of this parameter, the smoothness of the internal to the ellipse branch of the equidistant violates: it gains the «tails». Ro every point in scuh a tail, there exists a point in the ellipse within the distance $ h $. At the same time, there exists another point in the ellipse lying within the distance lesser than $ h_{} $! ♦

Representation of the equidistants to the ellipse in an algebraic form is possible with the aid of Theorem 2.

Th

**Theorem 4.** *Equidistants for the ellipse*

$$ \frac{x^2}{a^2}+\frac{y^2}{b^2}=1 $$
*are given implicitly by the equation* $ \Psi_h(x,y)=0 $ where
$$
\Psi_h(x,y)= {\mathcal D}_{\mu}\Bigg(
\mu^3-\left\{a^2+b^2-x^2-y^2+h^2 \right\}\mu^2 +
\left\{-a^2b^2\left(\frac{x^2}{a^2}+\frac{y^2}{b^2} -1 \right)+h^2(a^2+b^2) \right\}\mu -
h^2a^2b^2 \Bigg) \ .
$$
*Here* $ {\mathcal D}_{\mu} $ *stands for the discriminant of the polynomial treated with respect to * $ \mu_{} $, *whereas other variables should be considered as parameters.*

Ex

**Example.** Find the representation for the equidistants of the ellipse $ x^{2}/4+y^2=1 $ in the form of an algebraic equation.

**Solution.** One gets
$$ \Psi_h(x,y)=
{\mathcal D}_{\mu}(\mu^3-(5-x^2-y^2+h^2)\mu^2+(-x^2-4\,y^2+4+5\,h^2)\mu-4\,h^2)=
$$
$$
=9\,h^8-6(2\,x^2+7\,y^2+15)\,h^6+(-2\,x^4+73\,y^4+62\,x^2y^2-90\,x^2+270\,y^2+297)\,h^4+
$$
$$
+
(-56\,y^6-360\,y^2-62\,x^4-248\,y^4+4\,x^6+270\,x^2-90\,x^2y^4-30\,x^4y^2+140\,x^2y^2-360)\,h^2+
$$
$$
+4(x^4+2\,x^2y^2+y^4-6\,x^2+6\,y^2+9)(x^2/4+y^2-1)^2 \ .
$$
The equidistant equation: $ \Psi_h(x,y) = 0 $. Is it true that the inequality $ \Psi_h(x,y)<0 $ yields one the $ h_{} $-vicinity of the given ellipse? — The answer is positive for $ h\le 1/2 $ and negative for $ h>1/2 $. In the figure below, the domain $ \Psi_{7/8}(x,y)<0 $ is shadowed.
It turns out that $ \Psi_{7/8}(1,0)>0 $, whereas the distance from $ (1,0) $ to the ellipse (v. the solution to the example from
☝
SECTION) $ = \sqrt{2/3} \approx 0.8164965 < 7/8 = 0.875 $.
♦

Th

**Theorem ?.** *The square of the distance to the ellipsoid*

$$ a_{11}x^2+a_{22}y^2+a_{33}z^2 +2\,a_{13}xz+2\,a_{12}xy+2\,a_{23}yz+2\, b_1 x + 2\, b_2 y +2\, b_3 z -1 =0 $$
*from the point* $ (x_{0},y_0,z_0) $ * not lying in the ellipsoid,
equals the minimal positive zero of the* **distance equation**
$$
{\mathcal F}(u)={\mathcal D}_{\mu}(\Phi(\mu,u))=0
$$
*provided that this zero in not a multiple one. Here*
$$
\Phi(\mu,u)=
\left| \begin{array}{cccc}
a_{11}-\mu & a_{12} & a_{13} & b_1+\mu x_0 \\
a_{12} & a_{22}-\mu & a_{23} & b_{2}+\mu y_0 \\
a_{13} & a_{23} & a_{33}-\mu & b_3+\mu z_0 \\
b_1+\mu x_0 & b_2+\mu y_0 & b_3+\mu z_0 & -1 + \mu (u-x_0^2-y_0^2-z_0^2)
\end{array}
\right| \ ,
$$
*and*
$ {\mathcal D}_{} $ *stands for the discriminant of the polynomial* $ \Phi(\mu,u) $ *considered with respect to* $ \mu_{} $ *(whereas the remained variables are treated as parameters).*

Ex

**Example.** Find the distance from the point $ (6,7,8) $ to the ellipsoid

$$ 7\,x_1^2+6\,x_2^2+5\,x_3^2-4\,x_1x_2-4\,x_2x_3-3\,x_1-4\,x_2+5\,x_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) ,
$$
and
$$
\Phi(\mu,u)=
\left| \begin{array}{cccc}
7/18-\mu & -1/9 & 0 & -1/12+6\,\mu \\
-1/9 & 1/3-\mu & -1/9 & -1/9+7\,\mu \\
0 & -1/9 & 5/18-\mu & 5/36+8\,\mu \\
-1/12+6\,\mu & -1/9+7\,\mu & 5/36+8\,\mu & -1 + \mu (u-149)
\end{array}
\right|
$$
$$
=\mu^4u-(u-25)\mu^3-\left(-\frac{11}{36}\,u+\frac{12883}{648}\right)\mu^2-\left(\frac{1}{36}u-\frac{10949}{2916}\right)\mu+\frac{1621}{52488} \ .
$$
The discriminant of a quartic polynomial can be computed by the formula
$$
{\mathcal D}_{\mu}(A_0\mu^4+A_1\mu^3+A_2\mu^2+A_3\mu+A_4)=4\,I_2^3-27\,I_3^2 \ .
$$
Here
$$ I_2=4\,A_0A_4-A_1A_3 +\frac{1}{3}A_2^2 \ , $$
$$ I_3=-A_0A_3^2-A_1^2A_4+\frac{8}{3}A_0A_2A_4+ \frac{1}{3}A_1A_2A_3-\frac{2}{27}A_2^3 \ . $$
For our example this leads to
$$
{\mathcal F}(u) = {\mathcal D}_{\mu}(\Phi(\mu,u)) = 2^{-11}3^{-24} \Big( 38263752\,u^6+2599127028\,u^5-1635554407320\,u^4
$$
$$
-208679286534113\,u^3+3201333858779186\,u^2+1534445084940739328\,u+70891021564332120000 \Big) \ .
$$
This polynomial possesses exactly two positive zeros:
$$
u_1 \approx 91.969401, u_2 \approx 216.077674 \ .
$$
Distance from the given point to the ellipsoid equals $ \sqrt{u_1} \approx 9.590068 $, while the distance from that point to the farthest point in the ellipsoid equals $ \sqrt{u_2} \approx 14.699581 $.
♦

Solution to the problem of point-to-ellipse or point-to-ellipsoid distance evaluation presented in the previous sections is analytical and complete, that is, it provides one with a universal dependency of the distance as a function of the coefficients of the quadric an the point coordinates.
Unfortunately, this dependency is *implicit*: for the distance evaluation one has to resolve the algebraic distance equation. For any parameter specialization, this is possible with the aid of numerical methods.

Is it possible to extract from the distance equation *explicit* formulas for distance approximations as functions of the involved parameters?

Let us clarify the problem statement. In Theorem $ 2 $ from ☞ SECTION, the distance equation for the ellipse given in canonical form $ G(x,y)=x^2/a^2+y^2/b^2-1=0 $, is as follows $$ B_0z^4 + B_1z^3+B_2z^2+B_3z+B_4=0 $$ where $$ B_0=(a^2-b^2)^2,\dots, B_4= a^{4}b^{4}G^2(x_0,y_0) \left[(x_0^2+y_0^2-a^2-b^2)^2+4\,a^2b^2G(x_0,y_0)\right] $$ and the expressions for $ B_1,B_2,B_3 $ can be found ☞ HERE. If the point $ (x_0,y_0) $ lies close to the considered ellipse, one may assume that the minimal positive zero $ z_{\ast} $ of the distance equation is close to $ 0_{} $ and therefore can be approximated by the zero of the linearized approximation: $$ B_3z+B_4=0 \quad \Rightarrow \quad z_{\ast} \approx -B_4/B_3 \, . $$ In [?], the following formula is suggested for an approximation of the distance: $$ d \approx \sqrt{-B_4/B_3} \, . $$ Let us discuss the validity of this approximation.

Ex

**Example.**
Distance from the point $ x_0=a+1/2, y_0=0 $ to the ellipse $ x^2/a^2+y^2/25=1 $ equals $ 1/2 $ for any $ a\ne 0 $.
Calculate the distance approximations via the given formula:

$$ d\approx\frac{5}{4}\sqrt{-\frac{(8\,a+202)(4\,a+1)^2}{16\,a^4-792\,a^3-20999\,a^2-10400\,a-2550}} \ . $$ One has $$ \begin{array}{c|c|c|c|c|c|c|c} a & 5 & 10 & 30 & 60 & 67 & 68 & 69 \\ \hline \sqrt{-B_4/B_3} \approx & 0.499 & 0.511 & 0.605 & 1.245 & 2.786 & 4.282 & n/a \end{array} $$ For $ a=69 $ the radicand is negative. For this case, the formula becomes adequate to the reality if the point is taken closer to the ellipse, for instance, for the point $ x_0=69.1, y_0=0 $ it gives $ \approx 0.105 $. ♦

§

Explanaition of this fault ☞ HERE

We are interested in the alternatives to the suggested above approximation. We want these alternatives to be universal in the following meaning of this word: they should be applicable for the general form of the ellipse (ellipsoid) representation, i.e. not necessarily reduced to the canonical form. The last but not the least, we are in need of estimations of tolerances of these approximations.

Let us find the expansion of the zero of the equation in an appropriate power series. For the case of distance equation, let us choose the latter to be the one in powers of the value $ G_0= G(x_0,y_0) $ (correspondingly $ G_0=G(x_0,y_0,z_0) $). This value, in a neighborhood of the considered ellipse (or ellipsoid), can be treated as a small parameter. We restrict our treatment with computing the first three terms of this expansion:
$$
d^2=\ell_1 G_0+\ell_2 G_0^2+ \ell_3 G_0^3+\dots
$$
The value $ G_0 $ or $ |G_0 | $ is sometimes called **algebraic distance from the point to the ellipse** (**ellipsoid**),
while the true distance $ d $ is then referred to as the **geometric distance**.

Th

**Theorem.** *For the ellipsoid*

$$
G(x,y,z)=\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1 = 0
$$
*the two first approximations for the distance to it from the point* $ (x_0,y_0,z_0) $ *are given by the formulas*
$$
d_{(1)}=\frac{1}{2} \frac{|G_0|}{\sqrt{S_{4,0}}},
$$
$$
d_{(2)}=d_{(1)}\sqrt{1+\frac{1}{2} \frac{S_{6,0}}{S_{4,0}^2}G_0}
$$
*under assumption that the radicand in the last formula is nonnegative. Here*
$$ G_0=G(x_0,y_0,z_0),\ S_{4,0} = \frac{x_0^2}{a^4}+\frac{y_0^2}{b^4}+\frac{z_0^2}{c^4} ;\ S_{6,0}=\frac{x_0^2}{a^6}+\frac{y_0^2}{b^6}+\frac{z_0^2}{c^6} \, . $$

Generalization of this result to the case of a quadric in $ \mathbb R^n $ not necessarily represented in canonical form is as follows

Th

**Theorem.** *For the quadric*

$$
G(X)=X^{\top}AX+2\,B^{\top}X-1=0 \ , (A=A^{\top})
$$
*the first approximation formula for the distance to it from the point* $ X_0 \ne -A^{-1}B $ *is given by*
$$
d_{(1)} = \frac{1}{2}\cdot \frac{|G(X_0)|}{\sqrt{(AX_0+B)^{\top}({\bf A}X_0+B)}} \, ,
$$
*while the second one by*
$$
d_{(2)} = d_{(1)}
\sqrt{1+\frac{1}{2}\cdot \frac{({\bf A}X_0+B)^{\top}A(AX_0+B)}{[(AX_0+B)^{\top}(AX_0+B)]^2}G(X_0)} \, .
$$

Ex

**Example.** For the point $ (6,7,8) $, find distance approximations to the ellipsoid

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

**Solution.** The true distance is calculated via the distance equation construction in
☝
SECTION; $ B_5 $ and $ B_6 $ are the coefficients of $ z^1 $ and $ z^0 $ in this equation. Several other sample points are also included
$$
\begin{array}{c|c|c|c|c|c}
X_0 & \sqrt{-B_6/B_5} & d_{(1)} & d_{(2)} & d \\
\hline
(6,7,8) & n/a & 5.525 & 8.779 & 9.590 \\
\hline
(-4,4,3) & 3.390 & 2.877 & 3.526 & 4.732 \\
\hline
(-2,-2,4) & 3.187 & 2.409 & 2.907 & 3.647 \\
\hline
(1,-2,1) & 1.050 & 0.941 & 1.093 & 1.213 \\
\hline
(1,1,-1) & 0.656 & 0.861 & 0.420 & 0.664
\end{array}
$$

♦

The geometric interpretation for the approximation $ d_{(1)} $ is as follows.
This value coincides with the distance from the point $ X_0 $ to the linear manifold obtained by linearization of $ G(X) $ at the point^{2)} $ X_0 $:
$$ G(X_0)+ \operatorname{grad} \, (G)\bigg|_{X=X_0} (X-X_0) = 0 \ . $$
Here the row vector $ \operatorname{grad} \, (G)\bigg|_{X=X_0} $
stands for the gradient of the function $ G(X) $ calculated in the point $ X_0 $.
This formula was suggested in [?] for the distance approximation from a point $ X_0 $ to arbitrary algebraic manifold $ G(X)=0 $ in $ \mathbb R^n $.

Ex

**Example.** Ellipse $ x^2/18^2+y^2/5^2=1 $ (in red). Curves $ d_{(1)}=1,2,3 $ are represented in the figure.

The worst possible points for $ d_{(1)}=3 $ are marked in yellow. For the one external to the ellipse, the true distance value equals $ \approx 4.717 $.

For the distance approximation $ d_{(2)} $, the branches of the curves $ d_{(2)}=1,2,3 $ external to the ellipse are drawn in the figure

The true distance values at the worst possible points of $ d_{(2)}=3 $ (marked in blue) are $ \approx 2.932 $ and $ \approx 3.549 $. All the branches of the curve $ d_{(2)}=1 $ are presented in the figure below. There are tow branches lying inside the ellipse.

The internal to the ellipse branch of the curve $ d_{(2)}=2 $ does not circle the origin:

[1]. **Uteshev A.Yu., Yashina M.V.** *Metric Problems for Quadrics in Multidimensional Space.* J.Symbolic Computation, 2015, Vol. **68**, Part I, P. 287-315. Text
☞
ЗДЕСЬ (pdf)

[2]. **Uteshev A.Yu., Goncharova M.V.** *Point-to-ellipse and point-to-ellipsoid distance equation analysis.* J.Comput. Appl. Math., 2018, Vol. **328**, P. 232-251. Text
☞
HERE (pdf)

[?]. **Harker M., O'Leary P.** *First order geometric distance (the myth of Sampsonus)*, Proc. of the British Machine Vision Conference (BMVC06), I, 2006, Edinburgh, UK, P. 87–96.

[6]. **Sampson P.D.** *Fitting conic sections to very scattered data: an iterative refinement of the Bookstein algorithm.* Comput. Gr. Image Process., 1982, Vol. **18**, P.97-108

The factor $ a^{-8} b^{-8} $ is omitted.

Not the tangent manifold!

matricese/optimize/distancee/apollonius_e.txt · Последние изменения: 2021/06/03 23:07 — au