Center of Distance I am given $N$ points in a 2D plane($x$ and $y$ coordinates). I have to find a point in this plane with coordinates $X$ and $Y$ such that:    
$$\sum_{i=1}^N \max\{|X - A_i|, |Y - B_i|\}\text{ is minimized.}$$    
Here $A_i, B_i$ are the $x$ and $y$ coordinates of the $i$th point. My first thought was to find the centroid of all the $N$ points, but it does not seem to work. Is there any other special central point which satisfies the above property?
 A: Transform coordinates:
$$\begin{aligned}
 U_i &= \frac{A_i + B_i}{2}
& V_i &= \frac{A_i - B_i}{2}
\\ A_i &= U_i+V_i
& B_i &= U_i-V_i
\end{aligned}$$
Reason:
$$\max\{|\Delta A|,|\Delta B|\} =
\max\{|\Delta U+\Delta V|,|\Delta U-\Delta V|\}
= |\Delta U|+|\Delta V|$$
So now we look for coordinates $U,V$ minimizing
$$\sum_{i=1}^N \left(|U-U_i|+|V-V_i|\right)$$
which is more familiar.
The sum can be partitioned into two nonnegative parts, one independent from $V$
and the other independent from $U$. Therefore, the minimum is achieved
by selecting $U$ such that
$\sum_{i=1}^N |U-U_i|$ is minimized and $V$ such that
$\sum_{i=1}^N |V-V_i|$ is minimized.
An optimal $U$ is the median of all $U_i$. Why? Suppose there are $m$ coordinates below $U$ and $n$ above $U$,
then changing $U$ to $U+\Delta U$, with $\Delta U$ so small that $m$ and $n$ do not change in the process, results in $\sum_{i=1}^N |U-U_i|$ being offset by $(m-n)\Delta U$. Therefore, if $m>n$, $U$ should be decreased, and if $m<n$, $U$ should be increased.
(I have omitted considerations of coordinates equal to $U$, but you get the idea.)
Same goes for $V$. So the solution is:


*

*Transform the $(A_i,B_i)$ to $(U_i,V_i)$;

*Set $U$ to the median of the $U_i$ and $V$ to the median of the $V_i$;

*Transform back: $X = U+V$; $Y = U-V$.

