Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
This might be a duplicate. Check this answer: – Alex Lenail Mar 16 '15 at 3:09

Your Answer


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

Browse other questions tagged or ask your own question.