Chebyshev centroid, apparently fails in edge cases

Question

I am trying to find the centroid of a set of points under the Chebyshev distance. I wrote a program that apparently works for the cases that I tried but apparently gives incorrect answers for some edge cases that I do not have access to. [Meta remark: I would have marked this homework, but the tag is being obsoleted]

To get to the chase, the centroid is the point which has a minimum average distance to the set of points. The Chebyshev distance of two points p and q in two dimensions is

Also, I am restricted to points with integral co-ordinates.

This is my code:

sum_x=0; sum_y=0
for p in points:
    sum_x = sum_x + p[0]
    sum_y = sum_y + p[1]
center_x = int(sum_x/N)
center_y = int(sum_y/N)

directions = [(-1,-1),
     (-1,0),
     (-1,1),
     (0,-1),
     (0,0),
     (0,1),
     (1,-1),
     (1,0),
     (1,1)]

distances = [0] * len(directions)
for p in points:
    for i in range(len(directions)):
        distances[i] = distances[i] + max(abs(center_x+directions[i][0]-p[0]),abs(center_y+directions[i][1]-p[1]))

best_direction = min(range(len(directions)), key = lambda i:distances[i])

print "centroid = (", center_x+directions[best_direction][0],",", center_y+directions[best_direction][1],")"

print "total distance = ", distances[best_direction]

Here is my rationale: The Chebyshev metric is the same as the Manhattan distance under rotation in 2 dimensions. I basically find the Manhattan centroid, which is the same as the regular average of points, and then just search among the adjacent integral points to get the actual Chebyshev centroid. But I can't seem to find a bug in my code.

Answer 1

Your rationale is incorrect on one count. The Manhattan centroid is not the average of points. For instance, take the point set (0, 0); (1, 0); (100, 0). The average is (33.66, 0), but we could have done better by selecting (1, 0) instead. Do a couple more examples and you should see the real answer easily.

Also, you mention that the Chebyshev metric is equivalent to Manhattan distance under rotation, but you don't rotate the points anywhere in the code. This seems at least inconsistent: shouldn't you be calculating the Manhattan centroid in the rotated space instead?