I like to visit the various motor racing circuits in the UK throughout the year, and as a thought exercise I’ve been trying to think where the perfect location to build a house would be in order to live the shortest possible distance from each one.

I’ve mapped out each racing circuit on a graph, and now want to figure out the point which has the shortest straight-line distance to each point. I.e., what is the minimum total length of all the distances?

In the diagram below you can see the black points (racing circuits) with lines leading to my estimate of where the ideal location would be (blue point). This was just guesswork though, nothing mathematical.

Graph Map

I’ve simplified the coordinates. I’m guessing there’s a formula for this somewhere, possibly linked to the Shortest Distance problem or the Travelling Salesman problem?

Summary:

How can you calculate the point on a graph with the shortest total distance to multiple other points on a graph?

I’d love to know how it’s worked out, not just the answer! Thanks in advance.

Apologies if this has been asked before, but I can’t seem to find an exact match anywhere.

=================

1

en.wikipedia.org/wiki/Dijkstra%27s_algorithm, i think its helps

– Ricardo Gomes

2 days ago

Ricardo, it’s a different question. Emlyn is using graph in the sense of a plot on coordinates. Something more about the centre of mass would work better, if you know a particular algorithm for that?

– Nij

2 days ago

@Emlyn Washbrook For 3 points, it is Fermat point.

– Narasimham

2 days ago

=================

2 Answers

2

=================

This is a relatively simple, but somewhat involved exercise in basic Calculus (if we ignore road distance and deal only with straight-line distance at least), what you need to do is the following:

Get the coordinates for each track, this forms a set of points:

T={(x1,y1),…,(xn,yn)}T=\{(x_1,y_1),…,(x_n,y_n)\}

Then setup the equations giving the (euclidean) distances, did_i from an arbitrary point, (x,y)(x,y) to (xi,yi)(x_i,y_i).

The sum: s(x,y)=∑ni=1dis(x,y)=\sum_{i=1}^nd_i is now an equation of two variables, xx and yy which are the coordinates of an arbitrary point, it outputs the sum of the distances to each track from that point. The goal you seek now is to minimize that sum. This is done using a version of the first derivative test for functions of several variables.

The steps are the following:

Compute the first partial derivatives: ∂/∂x\partial/\partial x, and ∂/∂y\partial/\partial y.

Set them each equal to zero, and solve (note that you may get one variable as a function of the other in this case).

Find the intersection set of these two solutions (i.e. those points (x,y)(x,y) for which both partial derivatives are 00. These points are the critical points of the sum, ss.

All that remains is to compute the values of s(x,y)s(x,y) for the critical points and find the lowest one (there could be several points with the same minimum value).

As Justin Benfield answered, letting (X,Y)(X,Y) to be the coordinates of the unknown point, the distance to point (xi,yi)(x_i,y_i) is given by d2i=(X−xi)2+(Y−yi)2d_i^2=(X-x_i)^2+(Y-y_i)^2 and we want to minimize F=7∑i=1diF=\sum_{i=1}^7 d_i that is to say to find XX and YY such that dFdX=0,dFdY=0\frac{dF}{dX}=0 \qquad, \qquad \frac{dF}{dY}=0 Writing all of that means that you want dFdX=7∑i=1X−xi√(X−xi)2+(Y−yi)2=0\frac{dF}{dX}=\sum_{i=1}^7 \frac{X-x_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2}}=0 dFdY=7∑i=1Y−yi√(X−xi)2+(Y−yi)2=0\frac{dF}{dY}=\sum_{i=1}^7 \frac{Y-y_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2}}=0 which is quite complicated (in particular because of the interdependency of the unknown variables as already mentioned by Justin Benfield).

The problem becomes very simple if instead, you consider minimizing the sum of the squares of the distances that it is to say G=7∑i=1d2iG=\sum_{i=1}^7 d_i^2 In such a case, we havedGdX=27∑i=1(X−xi)=0,dGdY=27∑i=1(Y−yi)=0\frac{dG}{dX}=2\sum_{i=1}^7 (X-x_i)=0 \qquad , \qquad \frac{dG}{dY

}=2\sum_{i=1}^7 (Y-y_i)=0 which show that XX and YY are just the means of the xix_i’s and yiy_i’s.

Using your data points

(cityxyA7396B10581C139101D16565E14719F11549G10013)\left(

\begin{array}{ccc}

\text{city} & x & y \\

A & 73 & 96 \\

B & 105 & 81 \\

C & 139 & 101 \\

D & 165 & 65 \\

E & 147 & 19 \\

F & 115 & 49 \\

G & 100 & 13

\end{array}

\right)

this would just lead to X=8447≈120.6X=\frac{844} 7\approx 120.6 and Y=4247≈60.6Y=\frac{424} 7\approx 60.6. For such coordinates, we should have F≈288F\approx 288.

We can consider that this first step gives an approximate solution and we can start iterating the minimization of FF (this is quite tedious but perfectly doable). And guess what ? The solution is X≈118.2X\approx 118.2 and Y≈56.3Y\approx 56.3 for which F≈287F\approx 287. Not far, isn’t it ?

You could also take into account the fact you are going once a year to each of the cities except AA where you are going twice. The same procedure will put your place at X≈112.5X\approx 112.5 and Y≈67.5Y\approx 67.5. As you see, we can play a lot with this kind of problems.

But you could also say that what you want is to minimize the maximum distance to drive. Still more complicated but still doable, the result being X\approx 111.9X\approx 111.9 and Y\approx 59.3Y\approx 59.3. Still close !

Don’t worry ! You will learn this kind of things sooner or later and I am sure that you will enjoy them.