Расстояние Чебышёва

Расстояние Чебышёва (Chebyshev distance, $l_{\infty }$) — метрика, где расстояние между двумя точками равно максимальной разности координат по любой из осей.

Формула

Для двух точек $(x_1,y_1)$ и $(x_2,y_2)$:

$d=\max (|x_2-x_1|,|y_2-y_1|)$

В общем случае для $n$-мерных векторов:

$l_{\infty }(\vec{x},\vec{y})={\max }_{i=1,\dots ,n}|x_i-y_i|$

Аналогия с шахматным королём

Самый наглядный пример — ход короля на шахматной доске. Король движется в 8 направлениях (включая диагональ), и каждый ход — ровно 1 шаг.

Перемещение	Ходов
(0,0) → (3,0)	max(3, 0) = 3
(0,0) → (3,3)	max(3, 3) = 3
(0,0) → (3,5)	max(3, 5) = 5

Диагональный ход «бесплатно» покрывает оба направления одновременно.

Сравнение метрик расстояния

Метрика	Формула	Аналогия
Евклидова	$\sqrt{\Delta x^2+\Delta y^2}$	Прямая линия
Манхэттенская	$|\Delta x|+|\Delta y|$	Движение по кварталам города
Чебышёва	$\max (|\Delta x|,|\Delta y|)$	Ход короля на шахматной доске

Применение в алгоритмах

• LeetCode задачи с движением по сетке с диагоналями
• Кластеризация и поиск ближайших соседей в ML
• Игровые движки (движение по тайловым картам)

Пример кода (JavaScript)

// Time: O(n) | Space: O(1)
// Минимальное время посещения всех точек (LeetCode #1266)
var minTimeToVisitAllPoints = function(points) {
    let steps = 0;
 
    for (let i = 1; i < points.length; i++) {
        const [x1, y1] = points[i - 1];
        const [x2, y2] = points[i];
        steps += Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
    }
 
    return steps;
};