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 want to find the centroid (point which minimizes the sum of distances) of a set of points in the 2-dimensional plane using the Chebyshev distance ($\textbf{L}_\infty$ norm). I think the answer is not as simple as the $\textbf{L}_2$ norm (which is simply the mean of the $x$ and $y$ co-ordinates). I read in the wiki article on Manhattan distances that

A circle of radius r for the Chebyshev distance (Lāˆž metric) on a plane is also a square with side length 2r parallel to the coordinate axes, so planar Chebyshev distance can be viewed as equivalent by rotation and scaling to planar taxicab distance. However, this equivalence between L1 and Lāˆž metrics does not generalize to higher dimensions.

This would suggest that taking the median in the rotated co-ordinates would give the centroid under Chebyshev distances. However, I don't think all the grid points are mapped to grid points under this $45^o$ rotations. Does this matter?

share|improve this question
1  
What grid points? Yes, minimizing the sum of $L_\infty$ distances of points in the plane corresponds to minimizing the sum of $L_1$ distances after rotating by 45 degrees, and this can be obtained by medians in the rotated coordinates. –  Robert Israel Aug 17 '11 at 21:07

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.