\(L_1\) 距離空間は

\begin{align}
&|dx| + |dy| \\
=&\max(dx, -dx) + \max(dy, -dy) \\
=&\max(dx+dy,dx-dy,-dx+dy,-dx-dy) \\
=&\max(|dx+dy|,|dx-dy|) \\
=&\max(|dx’|,|dy’|) \\
\end{align}

によって \(L_\infty\) 距離空間になる。ただし、\(x’ = x + y, y’ = x – y\) と置いた。これは座標を45度回転していることに対応する。逆に辿れば \(L_\infty\) 距離空間は \(L_1\) 距離空間に変換できる。

\(L_1\) で解ける問題

• 点の集合 S が与えられる。\(v \in S\) がクエリで指定されるので、\(\sum_{u \in S} \mathrm{dist}(u, v)\) を求めよ（yuki1864）。

\(L_\infty\) で解ける問題

• 点の集合 S が与えられる。\(d \in \mathbb{R}\) がクエリで指定されるので、\(\mathrm{dist}(u, v) \leq d\) を満たす点の個数を求めよ（ABC233Ex）。
• 点の集合 S が与えられる。互いに距離が等しい3頂点がいくつがあるか求めよ（天下一2018E）。

\(L_\infty\)において、2点 u, v への距離が等しい領域は下図のようになる。