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?
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: