10.5 Geometry of minimising distance

In Module 5.5, we chose a point on a line to minimize total distance to fixed observations. A median minimized total absolute distance; a mean minimized total squared distance. What if the possible locations are points in a plane, or a device can only be placed on a particular road? The same optimization question now has a geometric interpretation.

This is intermediate coordinate geometry and optimization. Review Euclidean and Manhattan distance and the one-dimensional distance objective. OpenStax's coordinate lesson is a starting point for the distance formula.

A basic idea: choose a point in the plane

Suppose three locations are $(0,0)$, $(4,0)$, and $(2,6)$. We may place a hub at any point $(X,Y)$. If the cost is the sum of squared straight-line distances, each location contributes its horizontal difference squared plus its vertical difference squared. So the choice of $X$ controls one part of the cost, while the choice of $Y$ controls another.

The best horizontal coordinate is the mean of the locations' $x$ coordinates: $(0+4+2)/3=2$. The best vertical coordinate is the mean of their $y$ coordinates: $(0+0+6)/3=2$. Together they give the centroid $(2,2)$. It balances the three squared-distance penalties, even though no location lies there.

A quick tour of the geometry

For fixed locations $(x_i,y_i)$ and a proposed point $(X,Y)$, write the squared-distance cost as

$$Q(X,Y)=\sum_{i=1}^{n}\bigl[(X-x_i)^2+(Y-y_i)^2\bigr].$$

The $X$ and $Y$ terms separate. As in Module 5.5, completing the square in each coordinate gives

$$Q(X,Y)=n(X-\bar x)^2+n(Y-\bar y)^2+C, \qquad \bar x=\frac1n\sum_i x_i,\quad \bar y=\frac1n\sum_i y_i,$$

where $C$ does not depend on the chosen point. Thus $(\bar x,\bar y)$ is the unrestricted minimum. Every move away from it adds $n$ times the squared Euclidean distance of that move. If placement is restricted to a line or region, any allowed point closest to the centroid in Euclidean distance minimizes the cost. This is a geometric way to apply the feasible-region idea from Module 5.4.

The result depends on the cost. Total Manhattan distance separates into absolute horizontal and vertical differences, so coordinate-wise medians minimize it. Total ordinary Euclidean distance does not separate this way; its minimizer is called a geometric median, and finding it in general needs methods beyond this module. Do not replace either objective with squared distance unless the question says to do so.

Application 1: a hub for three sites

Sites are at $(0,0)$, $(4,0)$, and $(2,6)$. Where should an unrestricted hub go to minimize total squared Euclidean distance?

1. Average coordinates separately: $\bar x=2$ and $\bar y=2$, so choose $(2,2)$.
2. Its squared distances are $8$, $8$, and $16$, totaling $32$.
3. For comparison, $(2,0)$ gives $4+4+36=44$. The identity above shows that every other point costs more than $(2,2)$, not just this one.

Application 2: a device fixed to a rail

Targets are at $(0,0)$ and $(4,0)$, but a device must lie on the vertical rail $x=1$. Minimize the sum of its squared distances to the targets.

1. Without the rail, the centroid is $(2,0)$. The closest point to it on the rail is $(1,0)$, one unit to the left.
2. To check algebraically, any allowed point is $(1,Y)$ and its cost is $(1^2+Y^2)+(3^2+Y^2)=10+2Y^2$.
3. Because $Y^2\ge0$, the minimum is $10$ at $Y=0$. The rail changes the best location from $(2,0)$ to $(1,0)$.