Locating the HQ with Multi-focal Ellipses

Motivation

IrelandProvincialCapitalsMap Ireland has four provinces, the principal city in each being the provincial capital: Belfast, Cork, Dublin and Galway. The map here shows the location of these cities. Now imagine a company that needs to visit and to deliver goods frequently to all four cities. Where might they locate their HQ to minimize transport costs and travel times?

One possibility is to find the location with the smallest distance sum:

$\displaystyle d(\mathbf{r}_0) = \sum_{j=1}^{4} |\mathbf{r}_0-\mathbf{p}_j|$

where ${\mathbf{r}_0}$ is the position of the HQ and ${\mathbf{p}_j, j\in\{1,2,3,4\}}$ are the positions of the cities.

Common-or-Garden Ellipses

A gardener setting out an oval flower-bed uses a basic property of the mathematical curve called an ellipse. The ellipse is one of the conic sections, first studied by Apollonius of Perga (late 3rd, early 2nd centuries BC) in his book On Conics.

Ellipses occur frequently in physics, engineering and astronomy. An ellipse has two focal points or foci and the sum of the distances from the foci to any point on the curve is a constant that we denote as ${2a}$ . This allows us to draw an ellipse using pins and thread and enables gardeners to trace a flower-bed with two stakes and a piece of rope.

Gardener’s method of drawing an ellipse [Image Wikimedia].

The longest and shortest diameters of an ellipse, of length ${2a}$ and ${2b}$ , are called the major and minor axes. The “flatness” is measured by the eccentricity ${e}$ where ${e^2 = (a^2 - b^2)/a^2}$ . A circle has ${a = b}$ and ${e = 0}$ and the foci are co-located at the centre. The area of an ellipse is ${\pi ab}$ . We can see this by taking a circle of radius ${b}$ and stretcheing it in one direction by a factor ${a/b}$ , so that the area becomes ${A = (a/b)\pi b^2 = \pi ab}$ . The arc-length is much more complicated, involving a complete elliptic integral of the second kind: ${A = 4aE(e)}$ , where

$\displaystyle E(e) = \int_{0}^{\pi/2} \sqrt{ 1-e^2\sin^2\phi}\,d\phi$

We cannot express this in terms of elementary functions.

A Generalization: n-Ellipses

A circle with centre at ${\mathbf{p}_0}$ and radius ${k}$ is defined by the `level set’ ${|\mathbf{r}-\mathbf{p}_0| = k}$ . For an ellipse with foci at ${\mathbf{p}_1}$ and ${\mathbf{p}_2}$ we have

$\displaystyle |\mathbf{r}-\mathbf{p}_1| + |\mathbf{r}-\mathbf{p}_2| = k$

More generally, we consider a set of ${n}$ foci and define the distance sum

$\displaystyle d(\mathbf{r}) = \sum_{j=1}^{n} |\mathbf{r}-\mathbf{p}_j|$

The set of points ${\mathbf{r}}$ for which ${d(\mathbf{r}) = k}$ , the level set, is called an n-ellipse. Thus, a 1-ellipse is a circle and a 2-ellipse is a standard common-or-garden ellipse.

Sekino (1999) studied the level sets ${d(\mathbf{r}) = k}$ and found, for a fixed set of focal points ${\{ \mathbf{p}_1, \mathbf{p}_2, \dots \ \mathbf{p}_n \}}$ , a family of curves surrounding a fixed point, called the centre, which minimizes the distance sum.

Depending on the value of ${k}$ , the foci may lie within or outside the level curve. The distance sum is smooth (i.e., in ${C^\infty}$ ) on the plane with the foci removed. Moreover, Sekino showed that ${d(\mathbf{r})}$ has a unique global minimum at the centre. (This is for the generic case, when no three foci are colinear). If ${M}$ is the minimum value, every ${n}$ -ellipse with ${d(\mathbf{r})>M}$ is a piecewise smooth Jordan curve that divides the plane into two regions and the interior is convex.

The Motivating Problem

We return to the original problem. Suppose we must visit the four cities frequently, returning to the HQ each time. Then to minimize travel time we should locate the HQ at the centre of the family of 4-ellipses with foci at the four cities. The level curves are shown here.

Ireland-CentrePointMap

Contours, moving inward, are at 850, 800, 750, 700, 650, 600, 560 and 536.55km. Note the sharp corner of the contour (at 600km) through Galway. The centre — which gives the point of minimum distance sum to the four cities — is close to the town of Edenderry, County Offaly.

Conveniently, there is a small airstrip, Clonbullogue Airfield, located about 10 km south of Edenderry. Perhaps this is the “sweet spot” for some smart entrepreneur with a new business idea.

Coming Soon

Next week’s post will be about drawing an approximation to an n-ellipse using the gardener’s method with pencil and string.

Sources

${\bullet}$ Sekino, Junpei, 1999: n-Ellipses and the minimum distance sum problem. Am. Math. Month. 106, 193–202. PDF.

ThatsMaths