체비쇼프 거리(Chebyshev distance)는 수학에서 두 점 사이의 거리를 정의하는 지표(metric)의 하나로, 각 좌표 차원에 따른 차이의 절댓값 중 가장 큰 값을 거리로 삼는다. 러시아의 수학자 파프누티 체비쇼프(Pafnuty Lvovich Chebyshev, 1821~1894)의 이름을 따서 명명되었다. 최대 노름(maximum metric), L∞ 노름(L-infinity metric), sup 노름(sup metric) 또는 체스판 거리(chessboard distance)라고도 불린다.
정의
n차원 실수 좌표 공간에서 두 점 a = (a₁, a₂, ..., aₙ)과 b = (b₁, b₂, ..., bₙ) 사이의 체비쇼프 거리는 다음과 같이 정의된다.
D(a, b) = maxᵢ |aᵢ − bᵢ|
즉, 모든 좌표축에 대해 두 점의 차이의 절댓값을 구한 뒤, 그중 가장 큰 값을 거리로 간주한다. 이는 민코프스키 거리(Minkowski distance)에서 매개변수 p가 무한대로 발산할 때의 극한값에 해당한다.
기하학적 성질
2차원 평면에서 체비쇼프 거리로 측정할 때, 어떤 중심점으로부터 일정한 거리 r에 있는 점들의 집합(등거리 곡선)은 좌표축에 평행한 변을 가진 정사각형 형태를 이룬다. 이는 유클리드 거리에서의 원, 맨해튼 거리에서의 마름모(45도 회전된 정사각형)와 대비된다. 고차원으로 일반화할 경우, 체비쇼프 거리에서의 구(sphere)는 각 면이 좌표축에 수직인 초입방체(hypercube)가 된다.
체비쇼프 거리는 거리 공간의 네 가지 공리(비음성, 동일성, 대칭성, 삼각부등식)를 모두 만족한다.
체스판 거리로서의 해석
체비쇼프 거리는 체스 게임에서 킹(king)이 한 칸에서 다른 칸으로 이동하는 데 필요한 최소 이동 횟수와 같다. 킹은 상하좌우 및 대각선으로 한 칸씩 이동할 수 있으므로, 두 칸 사이의 x좌표 차이와 y좌표 차이 중 더 큰 값이 곧 필요한 최소 이동 횟수가 된다. 예를 들어, 체스판의 f6 칸과 e2 칸 사이의 체비쇼프 거리는 4이다. 이러한 이유로 체스판 거리(chessboard distance)라는 명칭이 붙었다.
응용 분야
체비쇼프 거리는 다음과 같은 분야에서 활용된다.
- 물류 창고 관리: 크레인이 x축과 y축을 동시에 움직일 수 있을 때, 물체를 이동시키는 데 소요되는 시간을 측정하는 데 사용된다.
- 전자 컴퓨터 지원 제조(CAM): 최적화 알고리즘에서 거리 척도로 활용된다.
- 이미지 처리 및 컴퓨터 비전: 픽셀 기반 연산에서 이웃 정의에 사용된다.
- 머신러닝: 특정 군집화 알고리즘 및 이상치 탐지에서, 한 차원에서의 큰 차이를 민감하게 감지해야 하는 경우에 적용된다.
- 게임 개발: 격자 기반 게임에서 대각선 이동이 가능한 캐릭터의 경로 탐색에 사용된다.
- 지리 정보 시스템(GIS): 격자형 도로망에서의 최단 경로 추정에 활용될 수 있다.
다른 거리 척도와의 관계
동일한 두 점에 대해 일반적으로 체비쇼프 거리는 유클리드 거리 및 맨해튼 거리보다 작거나 같다. 1차원에서는 모든 Lp 거리가 절댓값 차이로 동일해진다. 2차원에서 체비쇼프 거리는 맨해튼 거리를 45도 회전 및 스케일 변환한 것과 기하학적으로 동등하지만, 3차원 이상에서는 이러한 등가 관계가 성립하지 않는다.
