정의
체비쇼프 거리( Chebyshev distance )는 두 점 사이의 거리 측정 방법 중 하나로, 주로 격자(grid) 기반의 거리 계산에 사용된다. 2차원 또는 고차원 유클리드 공간에서 두 점 $p=(p_1,p_2,\dots ,p_n)$와 $q=(q_1,q_2,\dots ,q_n)$ 사이의 체비쇼프 거리는 다음과 같이 정의된다.
$$ d_{\text{Chebyshev}}(p,q)=\max_{i=1,\dots ,n};|p_i-q_i| $$
즉, 각 좌표축에 대한 절대 차이값 중 가장 큰 값을 거리로 채택한다.
수학적 성질
| 성질 | 설명 |
|---|---|
| 비대칭성 | 대칭성: $d(p,q)=d(q,p)$ |
| 양의 정의 | $d(p,q)\ge 0$이며, $d(p,q)=0$이면 $p=q$ |
| 삼각 부등식 | $d(p,r)\le d(p,q)+d(q,r)$ (거리의 기본 성질을 만족) |
| 정규화 | 좌표 변환에 따라 스케일링에 민감하지 않다(각 축의 단위가 동일할 경우). |
관계
체비쇼프 거리는 다음과 같은 다른 거리와 연관된다.
- 맨해튼 거리(ℓ₁ 거리): $\displaystyle d_{1}(p,q)=\sum_{i=1}^{n}|p_i-q_i|$
- 유클리드 거리(ℓ₂ 거리): $\displaystyle d_{2}(p,q)=\sqrt{\sum_{i=1}^{n}(p_i-q_i)^2}$
세 거리 모두 $\ell_p$ 거리 계열의 특수 경우이며, $\ell_\infty$ 거리라고도 부른다(무한 노름).
응용 분야
-
체스와 같은 격자 게임
- 체스에서 킹이 한 번에 이동할 수 있는 칸 수는 두 좌표 차이 중 큰 값과 동일하므로, 킹의 최소 이동 수는 두 위치 사이의 체비쇼프 거리가 된다.
-
이미지 처리
- 필터링이나 형태학적 연산에서 픽셀 간의 인접성을 정의할 때 체비쇼프 거리를 사용하면, 8-연결(8‑neighbourhood) 구조를 자연스럽게 모델링할 수 있다.
-
경로 탐색 알고리즘(A)*
- 격자 기반 맵에서 휴리스틱 함수로 사용하면, 실제 최단 경로 비용의 상한을 제공하면서도 계산이 간단해 효율적인 탐색이 가능하다.
-
데이터 클러스터링 및 군집 분석
- 고차원 데이터에서 각 차원의 스케일이 동일하거나 정규화된 경우, 체비쇼프 거리 기반 군집화가 특정 패턴을 강조하는 데 활용된다.
관련 용어
- ℓ∞ 노름: 무한 노름은 체비쇼프 거리와 동일한 수학적 정의를 갖는다.
- 맥스 노름(Maximum norm): 체비쇼프 거리의 다른 명칭.
참고
- Chebyshev distance. Wikipedia, The Free Encyclopedia.
- R. C. Gonzalez, R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018.
- P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 1968.