체비쇼프 거리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

체비쇼프 거리는 두 벡터 또는 점 사이의 거리를 계산하는 방법으로, 각 좌표별 차이의 절댓값 중 가장 큰 값을 사용한다. 이는 L_p 거리의 극한이며, L_∞ 거리라고도 불린다. 기하학적으로 체비쇼프 거리는 정사각형 형태의 원을 가지며, 체스판과 같은 격자에서 한 점의 무어 이웃을 정의하는 데 사용된다. 체비쇼프 거리는 창고 물류 및 컴퓨터 지원 제조(CAM) 분야에서 응용되며, L^∞-노름 및 균등 노름으로 일반화될 수 있다.

체비쇼프 거리

개요

{"caption":"체스판의 두 공간 사이의 이산 체비쇼프 거리는 킹이 두 공간 사이를 이동하는 데 필요한 최소 이동 횟수를 제공한다. 킹이 대각선으로 이동할 수 있기 때문에 행이나 열과 평행한 더 작은 거리를 커버하는 점프가 더 큰 거리를 커버하는 점프에 효과적으로 흡수되기 때문이다. 위는 정사각형 f6에서 각 정사각형의 체비쇼프 거리이다."}

정의

정의	거리 공간 (X,d)에서 두 점 x와 y 사이의 체비쇼프 거리는 다음과 같이 정의한다. d 체비쇼프 (x,y):= max i \|xi-yi\|. 즉, 각 좌표축을 따라 측정한 점 사이의 최대 차이이다.
동등한 정의	yi\| p ) 1 p. 따라서 L ∞ 메트릭이라고도 한다.

성질

응용

📚 더 읽어볼만한 페이지

수학적 체스 문제 - 맨해튼 거리
맨해튼 거리는 좌표축에 평행하게 측정한 거리 차이의 절댓값 합으로, 택시 기하학이라고도 불리며, 체스 룩의 이동이나 격자 도시 이동 거리 측정에 활용된다.
수학적 체스 문제 - 기사의 여행
기사의 여행은 체스판에서 나이트가 각 칸을 한 번씩 방문하는 경로를 찾는 수학 문제로, 오일러를 비롯한 다양한 분야의 사람들이 연구에 기여했으며, 체스판 크기에 따라 해답 존재 여부가 달라지고 다양한 알고리즘으로 해결 가능하다.
거리 - 민코프스키 거리
민코프스키 거리는 n차원 공간에서 두 점 사이의 거리를 정의하는 일반화된 방법으로, p값에 따라 맨해튼 거리, 유클리드 거리, 체비셰프 거리 등을 포함하며, 기계 학습에서 데이터 유사성 비교에 활용된다.
거리 - 맨해튼 거리
맨해튼 거리는 좌표축에 평행하게 측정한 거리 차이의 절댓값 합으로, 택시 기하학이라고도 불리며, 체스 룩의 이동이나 격자 도시 이동 거리 측정에 활용된다.
계량기하학 - 거리
거리는 수학에서 두 점 사이를 측정하는 함수, 물리학에서 물체의 위치 변화량, 일상생활에서 두 지점 사이의 길이를 의미하며, 국제단위계에서는 길이로 표현된다.
계량기하학 - 코시 열
코시 열은 무한수열에서 항들이 뒤로 갈수록 서로 가까워지는 수열로, 수렴열은 항상 코시 열이지만 그 역은 성립하지 않을 수 있으며, 실수의 완비성 정의 및 무한급수 수렴성 판정에 중요한 역할을 하는 개념이다.

1. 개요
2. 정의
3. 성질
4. 기하학적 특성
5. 일반화
6. 응용

2. 정의

두 벡터 또는 점 x와 y 사이의 체비쇼프 거리(표준 좌표는 각각 $x_i$ 와 $y_i$ )는 다음과 같다.

: $D(x,y) = \max_i(|x_i -y_i|).\$

이는 L_p 거리의 극한과 같으며, 다음과 같이 표현된다.

: $D(x,y)=\lim_{p \to \infty} \bigg( \sum_{i=1}^n \left| x_i - y_i \right|^p \bigg)^{1/p},$

따라서 L_∞ 거리라고도 알려져 있다.

수학적으로 체비쇼프 거리는 거리이며, 상한 노름 또는 균등 노름에 의해 유도된다. 이는 주입 거리의 한 예이다.

2차원, 즉 평면 기하학에서, 점 p와 q가 데카르트 좌표 $(x_1,y_1)$ 및 $(x_2,y_2)$ 를 갖는다면, 체비쇼프 거리는 다음과 같다.

: $D_{\rm Chebyshev} = \max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right ) .$

이 거리에 따르면, 중심점에서 체비쇼프 거리가 r인 점들의 집합인 원은 변의 길이가 2r이고 좌표축에 평행한 정사각형이다.

체스판에서, 연속적인 체비쇼프 거리가 아닌 이산 체비쇼프 거리를 사용할 때, 반지름 r의 원은 변의 길이가 2r인 정사각형이며, 각 변은 2r+1 개의 사각형을 포함한다. 예를 들어, 체스판에서 반지름 1의 원은 3×3 정사각형이다.

3. 성질

1차원에서는 모든 L_p 메트릭이 동일하며, 차이의 절댓값과 같다.

2차원에서 맨해튼 거리는 정사각형 형태의 "원", 즉 등고선을 가지며, 좌표축에 대해 π/4(45°) 각도로 정렬되어 있고, 변의 길이는 r이다. 따라서 평면 체비쇼프 거리는 회전 및 스케일링을 통해 평면 맨해튼 거리와 동등하게 볼 수 있다(즉, 선형 변환).

그러나 L₁과 L_∞ 메트릭 사이의 이러한 기하학적 동등성은 고차원으로 일반화되지 않는다. 체비쇼프 거리를 메트릭으로 사용하여 형성된 구는 각 면이 좌표축 중 하나에 수직인 정육면체이지만, 맨해튼 거리를 사용하여 형성된 구는 팔면체이다. 이들은 쌍대 다면체이지만, 정육면체 중에서 정사각형(및 1차원 선분)만이 자기 쌍대 다포체이다. 그럼에도 불구하고 모든 유한 차원 공간에서 L₁과 L_∞ 메트릭은 수학적으로 서로 이중적이다.

(체스판과 같은) 격자에서, 한 점으로부터 체비쇼프 거리 1에 있는 점들은 해당 점의 무어 이웃이다.

체비쇼프 거리는 $p$ 가 무한대에 도달할 때 차수- $p$ 민코프스키 거리의 극한 경우이다. 두 점 p, q 사이의 체비쇼프 거리는 다음과 같이 정의된다.

: $D_{\rm Chebyshev}(p,q) := \max_i(|p_i - q_i|)$

L_p-거리의 표현을 사용하면 다음과 같으며, 따라서 L_∞-거리라고도 불린다.

: $\lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k}$

2차원 공간에서 체비쇼프 거리는 다음과 같이 표현할 수 있다.

: $\max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right )$

체비쇼프 거리에서 반지름 r인 원은 한 변이 2r인 변이 축에 평행한 정사각형이 된다.

4. 기하학적 특성

두 점 p, q 사이의 체비쇼프 거리는 다음과 같이 정의된다.

: $D_{\rm Chebyshev}(p,q) := \max_i(|p_i - q_i|)$

L_p-거리의 표현을 사용하면 다음과 같으며, 따라서 L_∞-거리라고도 불린다.

: $\lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k}$

2차원 공간에서 체비쇼프 거리는 다음과 같이 표현할 수 있다.

: $\max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right )$

체비쇼프 거리에서 반지름 r인 원은 한 변이 2r인 변이 축에 평행한 정사각형이 된다.

5. 일반화

무한 길이 실수 또는 복소수 시퀀스의 시퀀스 공간의 경우, 체비쇼프 거리는 L^∞-노름으로 일반화된다. 이 노름은 때때로 체비쇼프 노름이라고 불린다. 실수 또는 복소수 값 함수의 공간의 경우, 체비쇼프 거리는 균등 노름으로 일반화된다.

두 점 p, q 사이의 체비쇼프 거리는 다음과 같이 정의된다.

: $D_{\rm Chebyshev}(p,q) := \max_i(|p_i - q_i|)$

L_p-거리의 표현을 사용하면 다음과 같으며, 따라서 L_∞-거리라고도 불린다.

: $\lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k}$

2차원 공간에서 체비쇼프 거리는 다음과 같이 표현할 수 있다.

: $\max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right )$

체비쇼프 거리에서 반지름 r인 원은 한 변이 2r인 변이 축에 평행한 정사각형이 된다.

6. 응용

체비쇼프 거리는 창고 물류에서 때때로 사용된다. 이는 천장 크레인이 물체를 이동시키는 데 걸리는 시간을 효과적으로 측정하기 때문이다(크레인은 x축과 y축에서 동시에 움직일 수 있지만 각 축을 따라 같은 속도로 움직인다).

또한 체비쇼프 거리는 전자 컴퓨터 지원 제조(CAM) 응용 분야, 특히 이러한 응용 분야의 최적화 알고리즘에서 널리 사용된다. 평면에서 작동하는 플로팅 또는 드릴링 머신, 포토플로터 등 많은 도구는 일반적으로 천장 크레인과 유사하게 x 및 y 방향의 두 개 모터로 제어된다.