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.

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|)$$

share|improve this question
    
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

1 Answer 1

You can use the equivalent linear program

$$\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.$$

share|improve this answer
    
+1, clever approach :) –  gt6989b Jul 17 '13 at 16:08
    
very clever approach :), but it is possible to find out the answer in O(n) time? I mean it is possible to get the answer in seconds with a compute even n = 100000? PS, I don't know how to use equivalent linear program till now :-) –  storm Jul 18 '13 at 7:33
    
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

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.