Сложный медианный вопрос

Дано n точек, выберите точку в данном списке так, чтобы сумма расстояний до этой точки была минимальной по сравнению со всеми остальными.

Расстояние измеряется в следующим образом.

Для точки (x, y) все 8 соседних точек имеют расстояние 1.

(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)

РЕДАКТИРОВАТЬ

Более четкое объяснение.

Функция foo определяется как

foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))

Найти точку x такая, что сумма ([foo (x, y) для y в list_of_points]) минимальна.

Пример

Вход:

12 -14
-3 3
-14 7
-14 -3
2 -12
-1 -6

Выход

-1 -6

Например: Расстояние между (4,5) и 6,7) равно 2.

Это можно сделать за O (n ^ 2) времени, проверив сумму каждой пары. Есть ли лучший алгоритм для этого?