Which point minimizes the total distance to N other points?

Question

I have a set of N points in a 2 (or 3) dimensional space. How do I find the point P for which the sum of distances to the N points is minimal?
Is there a known name for this problem?
Thanks.

The centroid minimizes the sum of the squares of the distances.

Answer 1

Apparently it is called the Fermat point (also called the isogonic center or the Rorricelli point) - see 1st and 3rd links. I spent two hours reading before I found that (there are at least 3248 distinct "centers" of a triangle - see 2nd link).
I wrongly thought it was the centroid.

For a triangle (N=3), there is an exact construction (but not computation) method to find the Fermat point -
http://en.wikipedia.org/wiki/Fermat_point

Construction To locate the Fermat point:

1) Construct three regular triangles out of the three sides of the given triangle.
2) For each new vertex of the regular triangle, draw a line from it to the opposite triangle's vertex.
3) These three lines intersect at the Fermat point.

[Note: For the case that the largest angle of the triangle exceeds 120°, the solution is a point on the vertex of that angle.]

jimloy.com comments:
The three angles at this point, between the vertices, are all 120 degrees. This point has many practical uses, as it is often a good idea to minimize distances, so save money. Telephone lines between three cities, using the minimum amount of wire, will be three lines which meet at the Fermat point.
_____________________________________

Here I calculated the Fermat point for the special case an isosceles triangle, translate it, rotate it and scale to get it into the plane so its coords are P(-1,0), Q(1,0), R(0,h)

Then by symmetry, the center you are looking for must have x=0. So it's at some point (0,y).

The sum of three distances is:
S = |-1,y| + |1,y| + |0,h-y| = 2√(y²+1) + h-y
dS/dy = y/√(y²+1) -1
dS/dy=0 => y/√(y²+1) -1 =0
y/√(y²+1) =1
y =√(y²+1)
y² = y²+1

The centroid C would obviously be (0,h/3)
at which point the sum S = 2√(1+ h²/9) + 2h/3

The Fermat point F is not at C
and at the F-point the sum S = S*.

You could compute general excess between the sum-of-distances S(y) and its optimum S*, show this is ≥0 and achieves 0 at F-point.
_____________________________________

And here is the exact construction or determination of the F-point for the isosceles triangle P(-1,0), Q(1,0), R(0,h):

The midpoint of PQ is (0,0) and the line L_R thru mid(PQ) and vertex R is thus x=0.

The midpoint of PR is (-1/2, h/2) and PR has slope +h.
Thus the constructed point Q' of the equilateral triangle on PR is (√3 h -1 , h - √3)/2
then the line L_Q thru constructed point Q' and vertex Q(1,0) is
y = (h-√3)/(√3 h -1) (x-1)

Constructed lines L_Q and L_R intersect at:
x = 0 =>
y = (h-√3)/(√3 h -1) (-1)
= -(h-√3)/(1- √3 h)
= -(h-√3)/(1- √3 h) * (1+ √3 h)/(1+ √3 h)
= -(h-√3)(1+ √3 h) /(1+ 3 h²)
= -(h + √3 h² -√3 -3h)/(1+ 3 h²)
= -(√3 h² -√3 -2h)/(1+ 3 h²)

Then by construction the F-point is
...

_____________________________________

[I deleted my previous (incorrect) derivation to verify if it was the centroid.]

Answer 2

first of all, impressive pastime slowfinger, i think of you will take the cake. whether, i've got no longer seen absolutely everyone arise with a friendly formal information of the shortest course. everybody is purely attempting to triumph over the final guy's course. for sure the shortest course from E to G would be a as we talk line diagonal. does not it make sense that the smallest area between a course from E to G and the line EG would yield the shortest course? absolutely everyone with me on that? possibly turn the diagram right into a coordinate airplane and the trails into purposes and get some integrals in contact? whether i'm uncertain if there is a impressive thank you to calculate that with no working laptop or laptop. And oh yeah, just to be gay, in accordance to the diagram, BC isn't unavoidably parallel to EF, so the bridge isn't unavoidably 21.40 9 gadgets long. outstanding problem.

Answer 3

The name you're looking for is "minimum aggregrate travel", or MAT, which is distinct from the centroid. See link to a discussion on this subject. There is no expression nor direct computational means for finding the point where MAT is minimum, numerical means must be resorted to.

Answer 4

This is a well-known geometric optimization problem, for 3 given points it is usually associated with Fermat's name, the general case in English language sources known as "minimum aggregate travel" as scythian notes above, the full solution was given, as far as I know, by Swiss mathematician Jacob Steiner in 19th century.
The complete analysis is somewhat lengthy to reproduce in an answer like this, I'll give a brief explanation of Steiner's results in planar case, the 3D-case is treated likely..

Existence and number of solutions: let Pi(xi, yi) /i=1,2,..,n/ are the given n points, P(x, y) - arbitrary point, then the sum of distances from P to all Pi:
f(x, y) = ∑[i=1..n] |PPi| =
= ∑[i=1, i=n] √((x - xi)² + (y - yi)²)
is a continuous function of 2 variables, if we consider it in the closed circle centered in the origin O with radius, equal to the greatest of distances |OPi|, thus encompassing all Pi, according the properties of continuous functions it surely reaches its minimum value in a point, say P0(x0, y0) in that circle. Using the triangle inequalities easily follows, that the same point P0 provides the minimum in the entire plane. Further, f(x, y) is a strictly convex function /also easy to prove/, such function can reach its minimum in ONE POINT ONLY, so P0 is unique.

Main property of the point P0: for strictly convex f(x,y) and for every unit vector e the directional derivative of f along e must be non-negative - that gives the following:
(1) if P0 is different from all Pi /i=1,2,...,n/ then the vector sum of all unit vectors from P to all Pi /a star-like configuration around P0/ must be equal to zero-vector;
(2) if P0 is coincident with any of Pi, say P1, the the vector sum of all unit vectors from P1 to all Pi /i=2,3,..,n/ must have length, less than or equal to 1.

How to find the optimal point: first check (2) above for every point Pi and if no one of them satisfies it, apply (1) - the latter means to solve the following system of 2 equations:
∑[i=1, i=n] (x - xi) /√((x - xi)² + (y - yi)²) = 0
∑[i=1, i=n] (y - yi) /√((x - xi)² + (y - yi)²) = 0,
according the above it has only one solution. This is the computational procedure not mentioned in other answers.

Examples:
n=3 - this case is covered precisely in smci's answer above - if the triangle P1P2P3 has no angle 120° or more, the optimal solution is the Fermat's point with "Mercedes" configuration of the 3 unit vectors, mentioned in (1) above, in the opposite case the optimal point is the vertex of the greatest angle - (2) above applies.
n=4 - if the quadrilateral P1P2P3P4 is convex, the required point is the intersection point of the diagonals with "X"-like configuration of unit vectors around it - case (1), otherwise if P1 is inside the triangle P2P3P4, it is the required point /case (2)/.