Minimize the sum of distance under maximum norm

Question

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.

Answer 1

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.