The geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the Fermat–Weber point or 1-median.^[1] Around 300 BC, the Greek mathematician Euclid laid down the rules of what has now come to be called Euclidean geometry, which is the study of the relationships between angles and distances in space. ... In probability theory and statistics, a median is a type of average that is described as the number dividing the higher half of a sample, a population, or a probability distribution, from the lower half. ... In statistics, central tendency is an average of a set of measurements, the word average being variously construed as mean, median, or other measure of location, depending on the context. ...

The geometric median is an important estimator of location in statistics. It is also a standard problem in facility location, where it models the problem of locating a facility to minimize the cost of transportation. In statistics, an estimator is a function of the observable sample data that is used to estimate an unknown population parameter; an estimate is the result from the actual application of the function to a particular set of data. ...

The special case of the problem for three points in the plane (that is, m = 3 and n = 2) is sometimes also known as Fermat's problem; it arises in the construction of minimal Steiner trees, and was originally posed as a problem by Pierre de Fermat to Evangelista Torricelli, who solved it. Its solution is now known as the Fermat point of the triangle formed by the three sample points. Alfred Weber's name is associated with the more general Fermat–Weber problem due to a discussion of the problem in his 1909 book on facility location. The Steiner tree problem is a problem in combinatorial optimization. ... Pierre de Fermat Pierre de Fermat IPA: (August 17, 1601–January 12, 1665) was a French lawyer at the Parlement of Toulouse, France, and a mathematician who is given credit for early developments that led to modern calculus. ... Evangelista Torricelli portrayed on the frontpage of Lezioni dEvangelista Torricelli. ... Construction for the fermat point. ... Alfred Weber (July 30, 1868 in Erfurt, Thuringia, Germany - May 2, 1958 in Heidelberg) was a German economist, sociologist and theoretician of culture whose work was influential in the development of modern economic geography. ...

Wesolowsky (1993) provides a survey of the problem. See Fekete, Mitchell, and Beurer (2003) for generalizations of the problem to non-discrete point sets.

Definition

Formally, for given a set of m points with each , the geometric median is defined as

Geometric Median

Note that argmin means the argument for which the sum is minimized. In this case, it is the point y from where the sum of all Euclidean distances to the x_i's is minimum. In mathematics, the Euclidean distance or Euclidean metric is the ordinary distance between two points that one would measure with a ruler, which can be proven by repeated application of the Pythagorean theorem. ...

Properties

• For the 1-dimensional case, the geometric median coincides with the median. This is because the univariate median also minimizes the sum of distances from the points.
• The geometric median is unique whenever the points are not collinear.
• The geometric median is equivariant for Euclidean similarity transformations, including translation and rotation. This means that one would get the same result either by transforming the geometric median, or by applying the same transformation to the sample data and finding the geometric median of the transformed data. This property follows from the fact that the geometric median is defined only from pairwise distances, and doesn't depend on the system of orthogonal Cartesian coordinates by which the sample data is represented. In contrast, the component-wise median for a multivariate data set is not in general rotation invariant, nor is it independent of the choice of coordinates.
• The geometric median has a breakdown point of 0.5.^[2] That is, up to half of the sample data may be arbitrarily corrupted, and the median of the samples will still provide a robust estimator for the location of the uncorrupted data.

In probability theory and statistics, a median is a type of average that is described as the number dividing the higher half of a sample, a population, or a probability distribution, from the lower half. ... Univariate describes a concept in statistics or econometrics. ... A line, or straight line, is, roughly speaking, an (infinitely) thin, (infinitely) long, straight geometrical object, i. ... In mathematics, an equivariant map is a function between two sets that commutes with the action of a group. ... // Two geometrical objects are called similar if one is congruent to the result of a uniform scaling (enlarging or shrinking) of the other. ... In Euclidean geometry, translation is a transformation of Euclidean space which moves every point by a fixed distance in the same direction. ... In the three-dimensional space, the possible moves of a rigid body are rotations and translations. ... Cartesian means relating to the French mathematician and philosopher Descartes, who, among other things, worked to merge algebra and Euclidean geometry. ... Robust statistics provides an alternative approach to classical statistical methods. ...

Special cases

• For 3 points, if any angle of the triangle is more than 120° then the geometric median is the point making that angle. If all the angles are less than 120°, the geometric median is the point inside the triangle which subtends an angle of 120° to all three pairs of points. This is also known as the Fermat point of the triangle formed by the three points.
• For 4 coplanar points, if a point is inside the triangle formed by the other three points, then the geometric median is that point. Otherwise, the points form a convex quadrilateral and the geometric median is where the diagonals of the quadrilateral intersect. This is also known as the Radon point of the four points.

Construction for the fermat point. ... A set of points is said to be coplanar if and only if they lie on the same geometric plane. ... In geometry, a quadrilateral is a polygon with four sides or edges and four vertices or corners. ...

Computation

Despite being an easy to understand concept, computing the geometric median poses a challenge. The centroid or center of mass, defined similarly to the geometric median as minimizing the sum of the squares of the distances to each sample, can be found by a simple formula — its coordinates are the averages of the coordinates of the samples — but no such formula is known for the geometric median, and it has been shown that no formula involving only arithmetic operations and kth roots can exist in general.^[3] Centroid of a triangle In geometry, the centroid or barycenter of an object in -dimensional space is the intersection of all hyperplanes that divide into two parts of equal moment about the hyperplane. ... In physics, the center of mass of a system of particles is a specific point at which, for many purposes, the systems mass behaves as if it were concentrated. ...

However, it is straightforward to calculate an approximation to the geometric median using an iterative procedure in which each step produces a more accurate approximation. Procedures of this type can be derived from the fact that the sum of distances is a convex function, since the distance to each sample point is convex and the sum of convex functions remains convex. Therefore, procedures that decrease the sum of distances at each step cannot get trapped in a local optimum. In mathematics, convex function is a real-valued function f defined on an interval (or on any convex subset C of some vector space), if for any two points x and y in its domain C and any t in [0,1], we have Convex function on an interval. ... local optimum is a term in Applied mathematics and Computer Science. ...

One common approach of this type, called Weiszfeld's algorithm^[4], is a form of iteratively re-weighted least squares. This algorithm defines a set of weights that are inversely proportional to the distances from the current estimate to the samples, and creates a new estimate that is the weighted average of the samples according to these weights. That is,

Bose et al (2003) describe more sophisticated geometric optimization procedures for finding approximately optimal solutions to this problem.

Implicit formula

If y is distinct from all the given points, x_j, then y is the geometric median if and only if it satisfies:

This is equivalent to:

which is closely related to Weiszfeld's algorithm.

If y is equal to some of the given points, then y is the geometric median if and only if there are vectors u_j such that:

where for x_j ≠ y,

and for x_j = y,

See also

• Central tendency
• Centroid, which minimizes the sum of squares of Euclidean distance
• Java applet demonstrating geometric median

In statistics, central tendency is an average of a set of measurements, the word average being variously construed as mean, median, or other measure of location, depending on the context. ... Centroid of a triangle In geometry, the centroid or barycenter of an object in -dimensional space is the intersection of all hyperplanes that divide into two parts of equal moment about the hyperplane. ...

Notes

1. ^ The more general k-median problem asks for the location of k cluster centers minimizing the sum of distances from each sample point to its nearest center.
2. ^ Lopuhaä and Rousseeuw (1991).
3. ^ Cockayne and Melzak (1969); Bajaj (1988).
4. ^ Weiszfeld (1937); Kuhn (1973); Chandrasekaran and Tamir (1989).

References

• Bajaj, C. (1988). "The algebraic degree of geometric optimization problems". Discrete and Computational Geometry 3: 177–191. DOI:10.1007/BF02187906. 

• Bose, Prosenjit; Maheshwari, Anil; Morin, Pat (2003). "Fast approximations for sums of distances, clustering and the Fermat–Weber problem". Computational Geometry: Theory and Applications 24 (3): 135–146. DOI:10.1016/S0925-7721(02)00102-5. 

• Chandrasekaran, R.; Tamir, A. (1989). "Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem". Mathematical Programming, Series A 44: 293–295. 

• Cockayne, E. J.; Melzak, Z. A. (1969). "Euclidean constructability in graph minimization problems.". Mathematics Magazine 42: 206–208. 

• Fekete, Sándor P.; Mitchell, Joseph S. B.; Beurer, Karin (2003). "On the continuous Fermat-Weber problem". arXiv:cs.CG/0310027. 

• Kuhn, Harold W. (1973). "A note on Fermat's problem". Mathematical Programming 4 (1): 98–107. DOI:10.1007/BF01584648. 

• Lopuhaä, Hendrick P.; Rousseeuw, Peter J. (1991). "Breakdown points of affine equivariant estimators of multivariate location and covariance matrices". Annals of Statistics 19: 229–248. 

• Weber, Alfred (1909). Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes. Tübingen: Mohr. 

• Wesolowsky, G. (1993). "The Weber problem: History and perspective". Location Science 1: 5–23. 

• Weiszfeld, E. (1937). "Sur le point pour lequel la somme des distances de n points donnes est minimum". Tohoku Math. Journal 43: 355–386.