체비쇼프 거리(Chebyshev distance)

체스의 킹은 가로, 세로, 대각선으로 한 칸씩 움직입니다. 한 수에 가로 차이와 세로 차이를 동시에 하나씩 줄일 수 있으니, 몇 수가 걸리는지는 두 차이 가운데 큰 쪽이 정합니다. $d = \max(|\Delta x|, |\Delta y|)$. 이것이 체비쇼프 거리입니다. 한 수에 각 좌표가 1보다 많이 줄 수는 없으니 이보다 빠를 수 없고, 대각선을 먼저 쓰면 정확히 이만큼에 닿습니다.

말을 로 고르고, 판에 를 적어 보겠습니다. 노란 말과 분홍 목표를 끌어 보세요. 지금 가로 차 , 세로 차 이고, 걸음 수는 , 가장 짧은 길은 가지입니다.

킹에게 같은 거리의 칸들은 정사각형 테두리를 이룹니다. 체비쇼프 거리의 '원'은 정사각형인 것입니다. 가로세로로만 한 칸씩 가는 말로 바꾸면 맨해튼 거리⁠(Manhattan distance)⁠가 되고 같은 거리의 칸들은 마름모가 됩니다. 최단 경로⁠(shortest path)⁠의 수도 이때는 이항계수⁠(binomial coefficient)⁠가 되어 파스칼의 삼각형⁠(Pascal's triangle)⁠이 판 위에 나타납니다. 판을 칸이 꼭짓점⁠(vertex)⁠인 그래프로 보면 두 거리 모두 최단 경로의 길이입니다.

평면에서 두 거리는 사실 같은 것을 45° 돌려 본 것입니다. $u = x + y$, $v = x - y$로 좌표를 바꾸면 $|\Delta x| + |\Delta y| = \max(|\Delta u|, |\Delta v|)$가 됩니다. 마름모를 돌리고 늘리면 정사각형이 되는 선형변환⁠(linear transformation)⁠입니다. 3차원부터는 이런 관계가 성립하지 않습니다. 3차원에서 L1의 '구'는 꼭짓점이 6개인 정팔면체이고 L∞의 '구'는 꼭짓점이 8개인 정육면체인데, 선형변환은 꼭짓점을 꼭짓점으로 보내므로 둘을 서로 바꿀 수 없습니다.

체비쇼프 거리는 Lp 노름⁠(Lp norm)⁠에서 p를 한없이 키운 극한이기도 합니다. 큰 수를 p제곱하면 작은 수들은 상대적으로 사라지니, p제곱 합의 p제곱근은 가장 큰 항만 남깁니다. 가로 모터와 세로 모터가 동시에 같은 속도⁠(velocity)⁠로 움직이는 기계라면 이동 시간이 바로 이 거리입니다.

이어지는 곳.

• 함수⁠(function)⁠ 사이에서는 '가장 크게 벌어진 곳의 차이' $\max_x |f(x) - g(x)|$가 같은 역할을 합니다. 이것을 균등 노름⁠(uniform norm)⁠이라 하고, 이 거리로 가까워지는 것이 균등 수렴⁠(uniform convergence)⁠입니다. 체비쇼프 거리라는 이름은 19세기 러시아 수학자 파프누티 체비쇼프에서 왔습니다. 그는 주어진 함수를 차수가 정해진 다항식⁠(polynomial)⁠으로 근사할 때, 가장 크게 벌어진 곳의 오차가 가장 작은 다항식을 찾는 문제를 연구했습니다(근사 이론⁠, approximation theory⁠).
• 테일러 다항식⁠(Taylor polynomial)⁠의 오차 한계도 구간 전체에서 가장 큰 오차, 곧 이 거리로 적힙니다.
• 푸리에 급수⁠(Fourier series)⁠로 계단 모양 함수를 근사하면 불연속점 근처에서 계단 높이의 약 9%만큼 튀어나옵니다(깁스 현상⁠, Gibbs phenomenon⁠). 항을 늘리면 튀어나온 부분은 점점 좁아져 오차를 제곱해 적분⁠(integral)⁠한 값은 0으로 가지만, 튀어나온 높이는 줄지 않습니다. 제곱 평균⁠(mean)⁠으로 재면 수렴⁠(convergence)⁠하지만 최대 오차로 재면 수렴하지 않는다는 뜻입니다.
• 이 거리로 그린 보로노이 다이어그램⁠(Voronoi diagram)⁠은 '원'이 정사각형이라 경계가 가로세로와 45° 선분으로 꺾입니다. 물론 세 규칙을 모두 지키는 거리 함수⁠(metric)⁠입니다.
• 거리를 늘리지 않는 사상을 화살표로 삼는 거리 공간⁠(metric space)⁠의 범주⁠(category)⁠에서, 보편 성질⁠(universal property)⁠로 정해지는 두 공간의 곱에 붙는 거리가 좌표 거리의 최댓값, 곧 체비쇼프 거리입니다(풍부화된 범주⁠(enriched category)⁠).