070 - Plant Planning（★4）の解説

この問題をネタに L1 ノルムの最小化の話をします。

平面上の点の集合 $(x_i,\,y_i)\ (i=1,2,\cdots,N)$ に対して、各点との「ユークリッド距離の2乗の話」

　 $\displaystyle E = \sum_{i=1}^N\left\{(x-x_i)^2+(y-y_i)^2\right\}$

を最小にする点 $(x,\,y)$ は、

　 $\displaystyle\frac{\partial E}{\partial x} = 0,\ \frac{\partial E}{\partial y} = 0$

の条件から、与えられた点の集合の重心に一致することがわかります。

　 $\displaystyle x = \frac{1}{N}\sum_{i=1}^Nx_i,\ y = \frac{1}{N}\sum_{i=1}^Ny_i$

平面上の点の集合 $(x_i,\,y_i)\ (i=1,2,\cdots,N)$ に対して、各点との「マンハッタン距離の話」

　 $\displaystyle E = \sum_{i=1}^N\left\{\sqrt{(x-x_i)^2}+\sqrt{(y-y_i)^2}\right\}$

を最小にする点 $(x,\,y)$ は、

　 $\displaystyle\frac{\partial E}{\partial x} = 0,\ \frac{\partial E}{\partial y} = 0$

の条件から決まります。上記の偏微分を実行すると、次の条件が得られます。

　 $\displaystyle \sum_{i=1}^N\frac{x-x_i}{|x-x_i|} = 0,\ \sum_{i=1}^N\frac{y-y_i}{|y-y_i|} = 0$

これは、次のように言い換えることができます。

　 $\displaystyle\sum_{i=1}^N{\rm sign}(x-x_i) = 0,\ \sum_{i=1}^N{\rm sign}(y-y_i) = 0$

つまり、 $x$ と $x_i$ の差の符号、つまり、 $x$ が $x_i$ の右にいるか、左にいるかの合計が 0 になればよく、 $x$ として、 $\{x_i\}_{i=1}^N$ の中央値を選択すればよいことになります。 $y$ についても同様です。

というわけで、非常にシンプルに問題の答えが得られます。

めもめも