Minimize the sum of distance under maximum norm Given a set of points (Xi, Yi). I need to find a point (doesn't have to be in the given set) that minimize the sum of distance to the other points. The tricky part is the distance is measured by max(|X-Xi|, |Y-Yi|).
I found it hard to reason about because of the max function. Algorithms that apply to manhattan distance don't seem to apply.

You want to find a point $(a,b)$ such that it is the solution to the following optimization problem:
\begin{align}
\min &\sum_i \max(|a-x_i|,|b-y_i|)
\end{align}
Let's do some voodoo.
\begin{align}
\min &\sum_i d_i\\
d_i&\geq|a-x_i| \qquad \forall i\\
d_i&\geq|b-y_i| \qquad \forall i\\
\end{align}
Let's do some more voodoo.
\begin{align}
\min &\sum_i d_i\\
d_i&\geq (a-x_i) \qquad \forall i\\
d_i&\geq -(a-x_i) \qquad \forall i\\
d_i&\geq (b-y_i) \qquad \forall i\\
d_i&\geq -(b-y_i) \qquad \forall i\\
\end{align}
Guess what? The problem is Linear and very simple to solve.
