Shortest Distance between two Ellipses or ellipsoids

Franz J. Vesely
July 2002 (last update Sep 2011)

Hard ellipsoids are popular in liquid crystal theory and simulation. The distance of a point from an ellipsoid, or between two ellipsoids, is notoriously hard to compute. Well-known recipes are due to Vieillard-Baron and to Perram and Wertheim; both are described in detail in Allen et al., Adv. Chem. Phys. Vol. LXXXVI, 1993, p.1. Two more recent attempts are:
Schlacken, Mögel, Schiller: 'Orientational transitions of twodimensional hard rod fluids', Molecular Physics, 1998, 93/5, 777;
Zheng and Palffy-Muhoray: 'Distance of closest approach of two arbitrary hard ellipses in 2D.' electronic-Liquid Crystal Communications January 18, 2007; www.e-lc.org/docs/2007_01_17_00_46_52.

Here I propose another method which is drawing from the method of constraint dynamics. The idea is to let a "glider" move along the rim of the ellipse/oid in question, subject to an attractive force from the extra point. The glider will obviously find the position of shortest distance to the point. If the extra point is itself a glider on another convex body, the two gliders will detect and assume the positions of smallest distance between the two rims, or surfaces.

Shortest distance of a point from an ellipse

There is, to my knowledge, no explicit solution. The straightforward tactics would be to
() Write down the general expression for a line normal to an ellipse, going through a yet unknown point on its rim
() Request that the given extra point lie on that line
() Determine the intersection of the line with the ellipse
This procedure leads to a fourth order equation.

In this situation a more physically-oriented strategy comes to mind:
() Assume a "glider" that may freely slip along the rim of the ellipse
() Assume an attractive force acting between the given extra point - which may be inside or outside the ellipse - and the glider
() The glider will obviously assume the position nearest to the given point

Such a strategy may be easily generalised to any convex curve, or body. Also, the extra point may itself be a glider on the contour or surface of a second curve or body, which would give us the shortest distance between two such objects.

Let the ellipse be given as
$ E_{1}: \;\;\;\left( \vec{r}-\vec{r}_{1}\right) \cdot C \cdot \left( \vec{r}-\vec{r}_{1}\right)-1=0 $    (1)

where $\vec{r}_{1}$ is the center of the ellipse and the matrix $C$ defines the lengths and directions of the axes.

To find the normal to $E_{1}$ through a point $G$ on its contour we interpret equ. (1) as a constraint equation,

$ \sigma(\vec{r}) \equiv \left( \vec{r}-\vec{r}_{1}\right) \cdot C \cdot \left( \vec{r}-\vec{r}_{1}\right)-1=0 $    (2)

and take the gradient of $\sigma$ at $G$:
$ \nabla_{G} \sigma = 2 \, C \cdot \left( \vec{r}_{G}-\vec{r}_{1}\right) $    (3)

Normalizing this vector we arrive at the normal direction vector $\vec{n}_{G}$. For later use we remark that the tangent to $E_{1}$ in point $G$ is given by

$ t_{G}: \;\;\; \left( \vec{r}_{G}-\vec{r}_{1}\right) \cdot C \cdot \left( \vec{r}-\vec{r}_{1}\right)-1=0 $    (4)

Given a point $2$ anywhere in the plane, we may now find the ellipse point closest to $\vec{r}_{2}$ by the following iterative scheme:


  • As a starting estimate, let $G$ be the intersection between the ellipse and a line going through $\vec{r}_{1}$ (the ellipse center) and $\vec{r}_{2}$. Any other initial position of the glider would do, but this is an economical choice.

  • Let the glider $G$ be attracted by $2$, its motion being restricted to the momentary tangent to $E_{1}$. Assuming a force $\vec{f}= k \, (\vec{r}_{2}-\vec{r}_{G})$ with an arbitrary spring constant $k$ we find

    $ \vec{r}_{G}'=\vec{r}_{G}+ a \,\left(\vec{f} - (\vec{f} \cdot \vec{n}_{G})\,\vec{n}_{G} \right) $    (5)

    where $a$ is another arbitrary coefficient. $k$ and $a$ should be chosen such that $ka \leq 1$.

  • The glider has now left the contour. To repair the constraint $\sigma$ we invoke the scheme due to Ryckaert et al. ( J. Comp. Phys. 23 (1977) 327.) Defining a constraint force

    $ \vec{s} = - \gamma \nabla_{G} \sigma(\vec{r}) = - \gamma \, 2 \, C \cdot \left( \vec{r}_{G}-\vec{r}_{1}\right) $    (6)

    we assume the glider to obey and move to

    $ \vec{r}_{G}''=\vec{r}_{G}'- a \, \gamma \, 2 \, C \cdot \left( \vec{r}_{G}-\vec{r}_{1}\right) $    (7)

    with

    $ \gamma = \frac{ \textstyle \sigma(\vec{r}_{G}')}{ \textstyle a \, \left( \nabla \sigma (G) \right)^{T} \cdot \nabla \sigma (G') } = \frac{\textstyle \sigma(\vec{r}_{G}')}{\textstyle 4 \, a \, \left( \vec{r}_{G}-\vec{r}_{1} \right)^{T} \cdot C^{T} \cdot C \cdot \left( \vec{r}_{G}'-\vec{r}_{1} \right) } $    (8)


  • The previous step has placed $G$ near but not exactly on the contour. We iterate by computing $\sigma(\vec{r}_{G}'')$ and reusing eqs. (7-8), with $\vec{r}_{G}''$ taking the place of $\vec{r}_{G}'$. This will land $G$ on $E_{1}$ after a very few steps.

  • If the normal at the new position of $G$ is already parallel to the force $\vec{f}$ we are finished. If not we have to do a few "outer" iterations according to eq. 5 etc.


F. J. Vesely / University of Vienna, 2002