Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@Hagen, thanks for the edit. I really wanted to do that but I couldn't figure out. –  Amit Tiwari Aug 11 '13 at 10:45
    
This is the only criteria. What I can do is take a starting point(such as centroid) and calculate the sum. Then I could shift that points and see the changes and try to get optimal solution. What I need to know is that which point should I choose as the starting point ? –  Amit Tiwari Aug 11 '13 at 11:21

1 Answer 1

up vote 2 down vote accepted

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:

  1. Transform the $(A_i,B_i)$ to $(U_i,V_i)$;
  2. Set $U$ to the median of the $U_i$ and $V$ to the median of the $V_i$;
  3. Transform back: $X = U+V$; $Y = U-V$.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.