最短总距离

在n维欧氏空间中，给定任意p( > 2)个点Pk，k = 1， 2，…, p, 我们需要找到一个点Q，使得它到每个点Pk的距离之和最小。这种点Q一定存在，可要具体找出来，却是很难很难。多面体的形心（centroid）不一定是Q点，某种加权平均或许能行。微积分的方法要解含有p个根式的方程，可是去掉平方根式后的高次多项式方程是无法解的。
当n=1时，问题很简单：把PK按顺序排列（可以重复），中间的任何一点都是解（当p为奇数时，只有一个解，p为偶数时有无穷多个解）。对于一般的n，如果采用绝对值（格点）距离，即定义两点P= (x1, x2, …, xn)，Q = (y1, y2, …, yn) 之间的距离为 sigma{|xi – yi|: i = 1, 2, …, n}，那么，还是找Pk的各个分量（坐标）的中位值即可。可偏偏人类习惯的却是欧氏距离，这还是Minkowski距离的特殊情形：d(P, Q) ^ r = sigma{ |xi – yi|^r, r = 1, 2, …, n}, r ≥ 1.
对于n = 2，即坐标平面的情形，p = 3时的解称为Fermat点：如果三角形有一个角至少是120度，那么，这个顶点就是要找的点。如果所有角都小于120度，Fermat点可以按如下方式作出：以任何一条边AB为边长，在三角形外部作一个等边三角形ABD；再作此等边三角形的外接圆。连接原三角形ABC的顶点C和D；CD与外接圆的交点就是Fermat点。其证明需要用到圆内几何的知识，如Ptolemy定理。
对于平面四边形的情形，如果是凸四边形（即每个内角都小于180度），那么，两条对角形的交点就是要找的点；这可以用三角形不等式很容易地证明。对于凹四边形，即有一个内角大于180度，那么，此顶点就是要找的点；这可以用余弦定理以及Heron公式来证明。一般地可以证明，对于一个钝角三角形，钝角处的两条邻边之和，小于其对边与2倍对边上的高之和。
对于平面上的其它m边形，为了找到一点Q = (x, y)，使得它到各点Pk的距离之和 S =: sigma{|QPk|: k = 1, 2, …, p} 达到最小，可以对x和y分别求偏导数，让它们等于零，得到两个根式方程。即使是p = 3，平方两次以消去根式后，得到的是x和y的12次方程组，那是很难解出的。Minkowski不等式，
sigma{sqrt[(x – xk)^2 + (y – yk)^2]: k = 1, 2, …, p} ≥ sqrt{[sigma|x – xk|]^2 + [sigma|y – yk|]^2} 
可以给出和式S的一个下界估计。右边的根式，当x取xk的中位值，y取yk的中位值时，达到最小。但是，这个最小值只有当|x - xk|与|y – yk|都成比例时才能够达到。AIME在1991年就出个一种特殊情形的问题，即要求使和式 sigma{sqrt[(2k-1)^2 + (ak)^2]: k = 1, 2, …, n} 最小，其中正实数ak之和等于17。用上述不等式，很容易得出答案。
假设点PK处具有质量（或电量）mk；那么这个质点系的质量中心是点Po = sigma{mkPk: k = 1, 2, …, p}/M，其中，M = sigma(mk)。由此，我们可以构造集合C = {sigma[ckPk]: ck 非负, 且和为1} 。质量中心是此集合中的一点。C是凸集，即对其中任意两个点P和Q，对任意的实数t在0与1之间，tP + (1-t)Q还在集合C中 。设P*是一个中位值点（当p为奇数时，此点唯一）；如果P*在凸集C中，则它就是要找的点。否则，我们找出P*到C的最短距离：min{d(P*, P): P ∈ C} = d(P, Q)，Q ∈ C，那么此点Q就是要找的点。这个结论的证明较难，我只能把它当作一个猜想；您若有兴趣的话，可以试着去证明或否定它。