曼哈顿距离与双绝对值最值

平面上的距离可以有不同定义。绝对值坐标差之和能转化成两个线性坐标的取大，因而适合处理双绝对值最值。

定义、三角不等式与等距线

对 $P(x_1,y_1),Q(x_2,y_2)$ 定义

d_1(P,Q)=|x_1-x_2|+|y_1-y_2|.

它非负、对称，且为零当且仅当 $P=Q$ ；逐坐标使用绝对值三角不等式，得到 $d_1(P,R)\le d_1(P,Q)+d_1(Q,R)$ 。

到原点的距离为 $r>0$ 的轨迹为 $|x|+|y|=r$ ，即顶点 $(\pm r,0),(0,\pm r)$ 的正方形边界； $r=0$ 时只有原点， $r<0$ 时无解。到一般定点的轨迹只需平移。

取 $A=(0,0),B=(1,1)$ 。若 $x\le0,y\ge1$ ，则

d_1((x,y),A)=-x+y=d_1((x,y),B).

所以等距轨迹包含整个无界二维区域，不能无条件称为“垂直平分折线”。一般求等距轨迹，应按两个定点的横、纵坐标分区间解绝对值方程；同一小区域内可能得到直线的一部分，也可能方程恒成立或无解。

对任意实数 $u,v$ ，同号与异号分类可得

|u|+|v|=\max\{|u+v|,|u-v|\}.

令 $s=x+y,t=x-y$ ，则两点的曼哈顿距离成为

d_1(P,Q)=\max\{|s_P-s_Q|,|t_P-t_Q|\}.

坐标可逆： $x=(s+t)/2,y=(s-t)/2$ 。这是一种线性换元，不是直接把原距离当作通常的欧氏距离。

给定非空有限点集 $P_i(x_i,y_i)$ ，记 $s_i=x_i+y_i,t_i=x_i-y_i$ 。若中心 $Q$ 可在整个平面自由选择，则

\min_Q\max_i d_1(P_i,Q)=\frac12\max\{s_{\max}-s_{\min},t_{\max}-t_{\min}\}.

任何中心到两个极端 $s$ 坐标的偏差最大值至少为其跨度的一半； $t$ 坐标同理，给出下界。取 $s_Q=(s_{\min}+s_{\max})/2,t_Q=(t_{\min}+t_{\max})/2$ 即同时满足上界，再反解 $Q$ 。

例如点 $(0,0),(2,0),(0,2)$ 的 $s$ 范围为 $[0,2]$ 、 $t$ 范围为 $[-2,2]$ ，最小半径为 $2$ ，可取 $Q=(1/2,1/2)$ 。最优中心未必唯一；若中心受额外轨迹约束，还必须检查上述选择是否可行。