# minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$

-
Looks like a small linear program. It's a guess, but I think the median of $x_i$ and $y_i$ will minimize (but solution is probably not unique in general). –  hardmath Jul 17 '13 at 15:33
$$\min_{t,x,y} \sum_{i=1}^n t_i\\ \text{subject to } -t_i\leq x-x_i\leq t_i\\ -t_i\leq y-y_i\leq t_i, \text{for }i=1,\dots,n.$$
Given that it is a particular linear program you might be able to solve it faster than a generic linear programming algorithm does, but I'm not sure if you can achieve $O(n)$ complexity. I don't know any fast algorithm off the top of my head, though. –  S.B. Jul 18 '13 at 13:36