平面α上有n个点(n＞1且n属于正整数)，如何作一点p,使得p到这n个点的距离之和最小?
平面α上有n个点(n＞1且n属于正整数)，如何作一点p,使得p到这n个点的距离之和最小?点p是否唯一?若唯一，是否存在一个通法求这个点的位置?
首先得看是什么「距离」.
- 如果是Manhattan distance, 很好做, 可参考 @dna049 的回答.
- 如果是squared Euclidean distance, 也很好做, 唯一最优解就是这p个点的mean.
- 如果是Euclidean distance, 这个问题叫Geometric median, 是离散/计算几何中一个非常经典的问题. 考虑平面上所有点在一条直线上, 这时问题可以退化到第一种曼哈顿距离的情况, 最优解就是这些点的median. 但是一般的Geometric median问题不是很好做, 一般情况的最优解没有显示表达式. 不过这个优化问题是凸的, 所以可以用各种凸优化演算法来得到一个近似解.
物理方法，在这几个点的位置固定圆环，n条绳子一端连接相同质量的砝码，另一端穿过环后连接于一点，松手，这个接点就是你要找的位置
首先注意到无论是平面，空间，m维空间，各个分量都相互不影响，所以不妨考虑直线上的情形：
假设这n个点从小到大依次为 。那么只要p满足
即可取得最小值（每次考虑最左边和最右边的两个点，即可证明）
所以 n 为奇数时，p是唯一的。n 为偶数时，一般不唯一
求解演算法复杂度 ，瓶颈在排序
如果所有的点都在一个平面的话，这个好说，n个点的重心就是你找的那个点p，在空间任意n个点的重心也是你要找的点p。开始解释：
首先你现在有n个点，假如是点 ，巧合的是你找到一个平面把这n个点包括在里面，这个平面存在，只要你能不断扩充维度就能找出来，但是如果只是平常的那个平面几何（欧几里得空间里面），在这个平面上你找两个基向量，这n个点的坐标就表示出来了，其实只要欧几里得空间，你找n个基向量这n个点都能被表示出来，就是坐标后边多写几个再回来，但是现在有意思的是你说的距离，两个点的距离你准备用哪种，最朴素的是两个点A，B，你把距离定义成
，就是两个点差先整成一个空间的一个点，再把这个「点」当成距离映到实数轴（差不多这样说，详细就看专业的书吧），这样微分等大量工具都能现成用，到了这一步可以开始写了：
先看第一种「平面「上的n个，基向量只有2个，所以所有点的坐标这样写：
......
简写一下: ,
实数轴上的距离有个好处，距离平方和和距离和有相同的变化趋势，而且这种变化会收束在同一个点（这个可以省略，但是不能忽视），所以可以大胆的用距离平方和代替距离和
现在假如P的坐标是
这个是距离和，
,这个是距离平方和，
用个字母表示下 ，距离和就先放著
再把上式在实数轴写一遍
,之后都用简写了，展开来自己展开
现在D随著x，y的值变化，空间中的n个点是你给的，这是「常量」
所以只要两个维度的变化率为0，就行了，求偏导
让上面两个等于0, 求解到重心坐标
，这个就是你要找的点P（欧几里得空间里面）
如果这n个点不在同一个平面内，（其实总能找到一个超平面给它们包进去），当然都是欧几里得空间里面，其他的我不清楚，没学
重心坐标点P具有相同的形式
假设点 ,简写了，就是一个点弄成n维坐标表示一下
重心就是
,就是相应坐标位置的和的平均值，
多几个方程求偏导就算出来了，自己算一下就理解了，按照楼上说法，我勉强回答了squared Euclidean distance时的一种处理方法.....
等同于求若干质点的重心。重心是唯一的。
唯一就是假命题。
假设这些点都在一条直线上，就不唯一。
简单点，n＝2。
在两点连线中间的所有点均为所求。
推荐阅读：
