平面α上有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。
在兩點連線中間的所有點均為所求。
推薦閱讀：
