What is the shortest possible distance from one point to multiple points?

1,769

As Justin Benfield answered, letting $(X,Y)$ to be the coordinates of the unknown point, the distance to point $(x_i,y_i)$ is given by $$d_i^2=(X-x_i)^2+(Y-y_i)^2$$ and we want to minimize $$F=\sum_{i=1}^7 d_i$$ that is to say to find $X$ and $Y$ such that $$\frac{dF}{dX}=0 \qquad, \qquad \frac{dF}{dY}=0$$ Writing all of that means that you want $$\frac{dF}{dX}=\sum_{i=1}^7 \frac{X-x_i}{\sqrt{(X-x_i)^2+(Y-y_i)^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=\sum_{i=1}^7 d_i^2$$ In such a case, we have$$\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 $X$ and $Y$ are just the means of the $x_i$'s and $y_i$'s.

Using your data points $$\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=\frac{844} 7\approx 120.6$ and $Y=\frac{424} 7\approx 60.6$. For such coordinates, we should have $F\approx 288$.

We can consider that this first step gives an approximate solution and we can start iterating the minimization of $F$ (this is quite tedious but perfectly doable). And guess what ? The solution is $X\approx 118.2$ and $Y\approx 56.3$ for which $F\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 $A$ where you are going twice. The same procedure will put your place at $X\approx 112.5$ and $Y\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.9$ and $Y\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.

Share:
1,769
Emlyn Washbrook
Author by

Emlyn Washbrook

Product designer with specialties in Solidworks and Keyshot.

Updated on October 22, 2020

Comments

  • Emlyn Washbrook
    Emlyn Washbrook about 3 years

    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.

    • Ricardo Gomes
      Ricardo Gomes about 7 years
    • Nij
      Nij about 7 years
      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?
    • Narasimham
      Narasimham about 7 years
      @Emlyn Washbrook For 3 points, it is Fermat point.
    • Claude Leibovici
      Claude Leibovici about 7 years
      Could you tell me what are the coordinates you guessed ?