How can I find an optimal point on a scatter graph?

Suppose I am going to locate an emergency point on a field having 100 houses.

If we see this as a scatter graph with 100 points on it, I need to find a point (or let’s call it an optimal point) which is the optimal choice for the emergency point. In other words, the SUM of travelling from the emergency point to all the houses (i.e. Emgncy point to Hous.No1 + Emgncy point to Hous.No2 + … Emgncy point to Hous.No100) is the lowest possible value.

Solutions Collecting From Web of "How can I find an optimal point on a scatter graph?"

I’ll attempt to explain the algorithm given at Wikipedia. Notice, though, that it isn’t a formula for the answer, but an algorithm for getting better and better approximations of the answer. Given a starting point, call it $y_0$, the algorithm produces a sequence of points $y_0,y_1,y_2,\dots$ converging (most of the time) to the answer.

So, call the points on your scatter graph $x_1,x_2,\dots,x_m$. Given two points $x$ and $y$, write $\|x-y\|$ for the distance between $x$ and $y$. Pick a starting point, $y_0$. [In principle, this could be anything. I suppose it might be a good idea to choose $y_0$ to be the average of the $x_j$, $y_0=(1/m)\sum_{j=1}^mx_j$. Or maybe choose $y_0$ so its first component is the median of the first components of the $x_j$, and its second component is the median of the second components of the $x_j$. I don’t know what’s best, and I don’t know how much difference it makes.]

Now if you have already computed the approximation $y_i$, you compute the next approximation, $y_{i+1}$, from the formula, $$y_{i+1}=\sum_{j=1}^m{x_j\over\|x_j-y_i\|}\div\sum_{j=1}^m{1\over\|x_j-y_i\|}$$ You keep computing better and better approximations, until they seem to converge to something, and then you’re done.