맨해튼 거리

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

1. 개요
2. 정의
- 2.1. 공식
- 2.2. 특징
3. 역사
4. 성질
5. 응용
참조

1. 개요

맨해튼 거리는 실수 좌표 공간에서 두 점 사이의 거리를 계산하는 방법 중 하나로, 각 좌표값 차이의 절댓값을 합하여 구한다. 이는 고정된 데카르트 좌표계를 기준으로 선분을 좌표축에 투영한 길이의 합으로 정의된다. 맨해튼 거리는 좌표계 회전에 의존하지만, 축의 반사나 평행 이동에는 변하지 않으며, 유클리드 공간에 겹쳐서 생각할 수 있다. 택시 기하학에서 원은 좌표축에 45° 기울어진 정사각형 모양을 가지며, 둘레는 8r이다. 맨해튼 거리는 체스에서 룩의 이동 거리를 측정하는 데 사용되며, 압축 센싱, 빈도 분포 차이 평가, 도시 계획 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

노름 - 작용소 노름
작용소 노름은 노름 공간 사이의 선형 변환의 크기를 측정하는 값으로, 선형 변환이 벡터의 크기를 얼마나 늘릴 수 있는지 나타내며 유계 작용소를 정의하고 분석하는 데 사용된다.
노름 - 절댓값
절댓값은 수의 크기를 0으로부터의 거리로 나타내는 수학적 개념으로, 실수에서는 x가 0보다 작을 때 -x, 복소수에서는 복소평면에서 원점으로부터의 거리로 정의되며, 비음성, 양의 정부호성, 곱셈에 대한 동질성, 삼각 부등식 등의 성질을 가진다.
수학적 체스 문제 - 체비쇼프 거리
체비쇼프 거리는 두 벡터 또는 점 사이의 거리 측정 방식으로, 각 좌표 성분 차이의 절댓값 중 최댓값으로 정의되며 L∞ 거리라고도 불린다.
수학적 체스 문제 - 기사의 여행
기사의 여행은 체스판에서 나이트가 각 칸을 한 번씩 방문하는 경로를 찾는 수학 문제로, 오일러를 비롯한 다양한 분야의 사람들이 연구에 기여했으며, 체스판 크기에 따라 해답 존재 여부가 달라지고 다양한 알고리즘으로 해결 가능하다.
거리 - 민코프스키 거리
민코프스키 거리는 n차원 공간에서 두 점 사이의 거리를 정의하는 일반화된 방법으로, p값에 따라 맨해튼 거리, 유클리드 거리, 체비셰프 거리 등을 포함하며, 기계 학습에서 데이터 유사성 비교에 활용된다.
거리 - 마할라노비스 거리
마할라노비스 거리는 확률 분포와 점 사이의 거리를 나타내는 척도로, 평균과 공분산 행렬을 사용하여 계산하며, 클러스터 분석, 통계적 분류, 이상치 탐지 등 다양한 분야에서 활용된다.

맨해튼 거리
개요
종류	거리 공간
다른 이름	택시 기하학 직각 기하학 맨해튼 거리 블록 거리
관련 개념	유클리드 거리 민코프스키 거리
특징
에서	동일한 거리

2. 정의

맨해튼 거리는 실수 좌표 공간에서 두 점 사이의 거리를 계산하는 방법 중 하나로, 각 좌표값 차이의 절댓값을 모두 더한 값이다. 보다 형식적으로는, n차원 공간에서 두 점 사이의 거리를 직교하는 좌표축을 따라 측정하여 정의한다.

2. 1. 공식

n차원 공간 벡터

\mathbf{p}=(p_1,p_2,\dots,p_n)\,

와

\mathbf{q}=(q_1,q_2,\dots,q_n)\,

가 있을 때, 맨해튼 거리

d_1(\mathbf{p}, \mathbf{q})

는 다음과 같이 정의된다.

:

d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|

예를 들어 평면 위의 두 점

(p_1,p_2)

과

(q_1,q_2)

사이의 맨해튼 거리는

| p_1 - q_1 | + | p_2 - q_2 |

이다.

2. 2. 특징

맨해튼 거리는 좌표계의 회전에는 의존하지만, 좌표축에 대한 반사나 평행이동에는 변하지 않는다. 맨해튼 거리는 SAS 합동(두 변과 그 사이 각이 같아도 합동이 아닐 수 있음)인 경우를 제외하면 모든 힐베르트 공리계(유클리드 기하학의 형식화)를 만족한다.^[1]

맨해튼 거리에서 원은 중심점에서 반지름이라고 불리는 일정한 거리만큼 떨어져 있는 점들의 집합이다. 유클리드 기하학과 맨해튼 거리의 원은 모양이 다르다. 맨해튼 거리에서 원은 좌표축에 45° 기울어진 정사각형이다. 모눈 크기가 줄어들면 수많은 점들은 연속적인 정사각형 모양을 만든다. 유클리드 거리를 이용해 각 변의 길이가 √2''r''이면 이 원의 반지름은 ''r''이다. 각 변의 길이를 맨해튼 거리로 측정한 값은 2''r''이다.

원의 반지름이자 체비쇼프 거리(Lp 거리)인 ''r''은 정사각형 평면에 평행하며, 정사각형의 변의 길이인 2''r''은 좌표축에 평행하다. 평면의 체비쇼프 거리는 거리의 회전과 축소된 평면의 맨해튼 거리와 같은 값이지만, L₁과 L_∞의 거리 사이의 같은 값은 보다 높은 차원에서 일반화되지 않는다.^[1] 유클리드 공간에 겹쳐진 추가적인 구조로 생각되는 택시 기하학적 거리는 좌표계의 방향에 따라 달라지며 공간의 유클리드 회전에 의해 변경되지만, 이동 또는 축 정렬 반사에는 영향을 받지 않는다. 택시 기하학은 힐베르트의 공리(유클리드 기하학의 형식화)의 모든 공리를 만족하지만, 각도의 합동은 유클리드 개념과 정확히 일치하도록 정의될 수 없으며, 택시 기하학적 각도의 합당한 정의 하에서는 변-각-변 공리가 만족되지 않아, 일반적으로 택시 기하학적으로 합동인 두 변과 그 사이의 택시 기하학적으로 합동인 각을 갖는 삼각형은 합동인 삼각형이 아니다.

3. 역사

1757년 로제르 조제프 보스코비치는 회귀 분석에서 적합도 척도로 ''L''¹ 메트릭을 사용했다.^[2] 19세기 후반 비유클리드 기하학이 발달하면서 기하학적 공간에서 점 사이의 거리로 해석되기 시작했다. 특히 1910년 프리제스 리에스와 헤르만 민코프스키의 연구에서 나타났으며, ''L''^p 공간 공식화는 리에스에게서 비롯되었는데, 택시 기하학은 여기에 특수한 경우로 포함된다.^[3] 헤르만 민코프스키는 수의 기하학을 발전시키면서, 이러한 공간이 노름 벡터 공간을 정의한다는 민코프스키 부등식을 확립했다.^[4]

''택시 기하학''이라는 이름은 1952년 카를 멩거가 시카고 과학산업 박물관에서 일반 대중을 위한 기하학 전시회와 함께 출판한 소책자 ''You Will Like Geometry''에서 처음 사용되었다.^[5]

4. 성질

맨해튼 거리에서 원은 중심점에서 반지름이라고 불리는 일정한 거리만큼 떨어져 있는 점들의 집합이다. 유클리드 기하학의 원과는 모양이 다른데, 맨해튼 거리에서 원은 좌표축에 45° 기울어진 정사각형 모양이다. 격자가 미세해짐에 따라 점들은 연속적인 정사각형 모양을 만든다. 유클리드 거리로 측정했을 때 각 변의 길이가 √2''r''이면 이 원의 반지름은 ''r''이다. 각 변의 길이를 맨해튼 거리로 측정하면 2''r''이 된다.^[1]

2차원 택시 기하학에서 원은 좌표축에 대해 대각선으로 정렬된 정사각형이다. 파란색 중심에서 고정된 거리에 있는 정사각형 격자 위의 모든 점의 집합은 빨간색으로 표시된다. 격자가 더 미세해지면 빨간색 점의 수가 늘어나고, 극한에서는 연속적인 기울어진 정사각형이 된다. 각 변의 택시 길이는 2''r''이므로, 둘레는 8''r''이다. 따라서 택시 기하학에서 원의 상수 π의 유사값, 즉 둘레와 지름의 비율은 4이다.^[1]

택시 기하학은 힐베르트의 공리(유클리드 기하학의 형식화)의 모든 공리를 만족하지만, 각도의 합동은 유클리드 개념과 정확히 일치하도록 정의될 수 없으며, 택시 기하학적 각도의 합당한 정의 하에서는 변-각-변 공리가 만족되지 않는다. 일반적으로 택시 기하학적으로 합동인 두 변과 그 사이의 택시 기하학적으로 합동인 각을 갖는 삼각형은 합동인 삼각형이 아니다.

택시 기하학에서 두 개의 직각 이등변 삼각형. 세 각과 두 변은 합동이지만 삼각형은 합동이 아니다. 따라서 ASASA는 택시 기하학에서 합동 정리가 아니다.

두 삼각형은 세 쌍의 대응변의 거리가 같고 세 쌍의 대응각의 크기가 같을 때 합동이다. 삼각형 합동을 보장하는 몇 가지 정리가 유클리드 기하학에 존재하는데, 이는 각-각-변(AAS), 각-변-각(ASA), 변-각-변(SAS), 변-변-변(SSS)이다. 그러나 택시 기하학에서는 SASAS만이 삼각형 합동을 보장한다.^[11] 예를 들어, 45-90-45의 각을 갖는 두 개의 직각 이등변 택시 기하학 삼각형을 생각해 보자. 두 삼각형의 두 변은 택시 기하학적 길이가 2이지만, 빗변은 합동이 아니다. 이 반례는 AAS, ASA 및 SAS를 제거한다. 또한 AASS, AAAS, 심지어 ASASA도 제거한다. 세 개의 합동인 각과 두 변을 갖는다고 해서 택시 기하학에서 삼각형의 합동이 보장되는 것은 아니다. 따라서 택시 기하학에서 유일한 삼각형 합동 정리는 SASAS이며, 세 쌍의 대응변 모두 합동이어야 하고, 적어도 두 쌍의 대응각이 합동이어야 한다.^[12]

4. 1. 원 (Sphere)

맨해튼 거리에서 원은 중심점에서 반지름이라고 불리는 일정한 거리만큼 떨어져 있는 점들의 집합이다. 유클리드 기하학의 원과는 모양이 다른데, 맨해튼 거리에서 원은 좌표축에 45° 기울어진 정사각형 모양이다. 격자가 미세해짐에 따라 점들은 연속적인 정사각형 모양을 만든다. 유클리드 거리로 측정했을 때 각 변의 길이가 √2''r''이면 이 원의 반지름은 ''r''이다. 각 변의 길이를 맨해튼 거리로 측정하면 2''r''이 된다.^[1]

2차원 택시 기하학에서 원은 좌표축에 대해 대각선으로 정렬된 정사각형이다. 파란색 중심에서 고정된 거리에 있는 정사각형 격자 위의 모든 점의 집합은 빨간색으로 표시된다. 격자가 더 미세해지면 빨간색 점의 수가 늘어나고, 극한에서는 연속적인 기울어진 정사각형이 된다. 각 변의 택시 길이는 2''r''이므로, 둘레는 8''r''이다. 따라서 택시 기하학에서 원의 상수 π의 유사값, 즉 둘레와 지름의 비율은 4이다.^[1]

4. 2. 호의 길이 (Arc length)

함수

y = f(x)

가 연속적으로 미분 가능한 함수라고 할 때,

s

를 어떤 구간

[a,b]

에서

f

의 그래프의 택시 호의 길이라고 하자. 이 구간을 무한소 하위 구간으로 분할하고,

\Delta s_i

를

i^{\text{th}}

호의 택시 길이라고 하면,^[6]

\Delta s_i = \Delta x_i + \Delta y_i = \Delta x_i+ |f(x_i) - f(x_{i-1})|.

평균값 정리에 의해,

x_i

와

x_{i-1}

사이에

f(x_i) - f(x_{i-1}) = f'(x^*_i)dx_i

를 만족하는 어떤 점

x^*_i

가 존재한다.^[7] 그러면 이전 방정식은 다음과 같이 쓸 수 있다.

\Delta s_i = \Delta x_i + |f'(x^*_i)|\Delta x_i = \Delta x_i(1+|f'(x^*_i)|).

그러면

s

는

[a,b]

에서

s

의 모든 분할의 합으로 주어지며, 이 분할이 임의로 작아질 때이다.

단조 증가 또는 감소 함수로 정의된 곡선은 동일한 끝점을 공유하는 한 택시 호의 길이가 동일하다.

\begin{align}s &= \lim_{n \rightarrow \infty} \sum_{i=1}^{n} \Delta x_i(1+|f'(x^*_i)|) \\& = \int_{a}^{b} 1+|f'(x)| \,dx\end{align}

이것을 테스트하기 위해 원점을 중심으로 하는 반지름

r

의 택시 원을 사용한다. 첫 번째 사분면에서의 곡선은

f(x)=-x+r

로 주어지며, 그 길이는

s = \int_{0}^{r} 1+|-1|dx = 2r

이 값을

4

로 곱하여 나머지 사분면을 고려하면

8r

이 되며, 이는 택시 원의 원둘레와 일치한다.^[8]

이제 원점을 중심으로 하는 반지름

r

의 유클리드 원을 사용하는데, 이는

f(x) = \sqrt{r^2-x^2}

로 주어진다. 첫 번째 사분면에서의 호의 길이는 다음과 같다.

\begin{align}s &= \int_{0}^{r} 1+|\frac{-x}{\sqrt{r^2 - x^2}}|dx\\&= x+\sqrt{r^2-x^2} \bigg|^{r}_{0}\\&= r-(-r)\\&= 2r\end{align}

나머지 사분면을 고려하면 다시

4 \times 2r = 8r

이 된다. 따라서, 택시 메트릭에서 택시 원과 유클리드 원의 원둘레는 같다.^[9] 실제로, 구간

[a,b]

에서 연속적인 도함수를 갖는 단조롭고 미분 가능한 모든 함수

f

에 대해,

[a, b]

에서

f

의 호의 길이는

(b-a) + \mid f(b)-f(a) \mid

이다.^[10]

4. 3. 삼각형 합동 (Triangle congruence)

유클리드 공간에 겹쳐진 추가적인 구조로 생각되는 택시 기하학적 거리는 좌표계의 방향에 따라 달라지며 공간의 유클리드 회전에 의해 변경되지만, 이동 또는 축 정렬 반사에는 영향을 받지 않는다. 택시 기하학은 힐베르트의 공리 (유클리드 기하학의 형식화)의 모든 공리를 만족하지만, 각도의 합동은 유클리드 개념과 정확히 일치하도록 정의될 수 없으며, 택시 기하학적 각도의 합당한 정의 하에서는 변-각-변 공리가 만족되지 않아, 일반적으로 택시 기하학적으로 합동인 두 변과 그 사이의 택시 기하학적으로 합동인 각을 갖는 삼각형은 합동인 삼각형이 아니다.

두 삼각형은 세 쌍의 대응변의 거리가 같고 세 쌍의 대응각의 크기가 같을 때 합동이다. 삼각형 합동을 보장하는 몇 가지 정리가 유클리드 기하학에 존재하는데, 이는 각-각-변(AAS), 각-변-각(ASA), 변-각-변(SAS), 변-변-변(SSS)이다. 그러나 택시 기하학에서는 SASAS만이 삼각형 합동을 보장한다.^[11]

예를 들어, 45-90-45의 각을 갖는 두 개의 직각 이등변 택시 기하학 삼각형을 생각해 보자. 두 삼각형의 두 변은 택시 기하학적 길이가 2이지만, 빗변은 합동이 아니다. 이 반례는 AAS, ASA 및 SAS를 제거한다. 또한 AASS, AAAS, 심지어 ASASA도 제거한다. 세 개의 합동인 각과 두 변을 갖는다고 해서 택시 기하학에서 삼각형의 합동이 보장되는 것은 아니다. 따라서 택시 기하학에서 유일한 삼각형 합동 정리는 SASAS이며, 세 쌍의 대응변 모두 합동이어야 하고, 적어도 두 쌍의 대응각이 합동이어야 한다.^[12] 이 결과는 택시 기하학에서 선분의 길이가 방향에 따라 달라진다는 사실에 기인한다.

5. 응용

체스에서 룩은 체스판의 정사각형 사이 거리를 맨해튼 거리로 측정한다.^[1] 킹과 퀸은 체비쇼프 거리를 사용하며, 비숍은 체스판을 45도 회전시킨 맨해튼 거리(같은 색의 정사각형)를 사용한다.^[1]

부정 방정식의 해를 구할 때, 파라미터 벡터에 대한 정규화 항은 벡터의 $\ell_1$ 노름(택시 기하학)으로 표현된다.^[13] 이러한 접근 방식은 압축 센싱이라고 하는 신호 복구 프레임워크에 나타난다.

택시 기하학은 이산적인 빈도 분포의 차이를 평가하는 데 사용될 수 있다. 예를 들어, RNA 스플라이싱에서 각 육량체가 스플라이스 부위 근처의 각 특정 뉴클레오타이드에서 나타날 확률을 나타내는 육량체의 위치 분포는 L1 거리로 비교할 수 있다.^[14] 각 위치 분포는 각 항목이 특정 뉴클레오타이드에서 시작하는 육량체의 가능성을 나타내는 벡터로 표현될 수 있다. 두 벡터 간의 큰 L1 거리는 분포의 특성에 상당한 차이가 있음을 나타내는 반면, 작은 거리는 유사한 형태의 분포를 나타낸다. 이는 각 세그먼트의 면적이 해당 지점에서 두 곡선의 가능성의 절대 차이이므로 두 분포 곡선 사이의 면적을 측정하는 것과 같다. 모든 세그먼트에 대해 합산하면 L1 거리와 동일한 측정값을 제공한다.^[14]

5. 1. 체스

체스에서 룩은 체스판의 정사각형 사이 거리를 맨해튼 거리로 측정한다.^[1] 킹과 퀸은 체비쇼프 거리를 사용하며, 비숍은 체스판을 45도 회전시킨 맨해튼 거리(같은 색의 정사각형)를 사용한다.^[1] 즉, 비숍은 체스판의 대각선 방향으로 거리를 측정한다.^[1] 따라서 킹만 한 번 움직일 때 거리와 같은 수만큼 이동하고, 룩, 퀸, 비숍은 일정한 거리를 이동하기 위해 한 번 또는 두 번 움직여야 한다.^[1] (단, 비어 있는 체스판을 가정하고, 비숍은 이동 가능한 모든 경우를 가정한다.)^[1]

5. 2. 압축 센싱 (Compressed sensing)

부정 방정식의 해를 구할 때, 파라미터 벡터에 대한 정규화 항은 벡터의

\ell_1

노름(택시 기하학)으로 표현된다.^[13] 이러한 접근 방식은 압축 센싱이라고 하는 신호 복구 프레임워크에 나타난다.

5. 3. 빈도 분포 차이 (Differences of frequency distributions)

택시 기하학은 이산적인 빈도 분포의 차이를 평가하는 데 사용될 수 있다. 예를 들어, RNA 스플라이싱에서 각 육량체가 스플라이스 부위 근처의 각 특정 뉴클레오타이드에서 나타날 확률을 나타내는 육량체의 위치 분포는 L1 거리로 비교할 수 있다.^[14] 각 위치 분포는 각 항목이 특정 뉴클레오타이드에서 시작하는 육량체의 가능성을 나타내는 벡터로 표현될 수 있다. 두 벡터 간의 큰 L1 거리는 분포의 특성에 상당한 차이가 있음을 나타내는 반면, 작은 거리는 유사한 형태의 분포를 나타낸다. 이는 각 세그먼트의 면적이 해당 지점에서 두 곡선의 가능성의 절대 차이이므로 두 분포 곡선 사이의 면적을 측정하는 것과 같다. 모든 세그먼트에 대해 합산하면 L1 거리와 동일한 측정값을 제공한다.^[14]

5. 4. 도시 계획 (Urban Planning)

맨해튼 거리는 '''시가지 블록 거리'''라고도 한다. 맨해튼 거리라는 이름은 맨해튼과 같이 정방형 블록으로 구획된 도시에서 자동차가 주행하는 거리에 기인한다. 한 모서리에서 동쪽으로 3블록, 북쪽으로 6블록 떨어진 모서리로 이동하려면, 어떤 경로를 따르더라도 최소 9블록을 통과해야 한다.^[1]

체스에서는 룩에게 있어서 말칸 사이의 거리는 맨해튼 거리에 의해 측정된다. 킹, 퀸, 비숍은 체비쇼프 거리를 사용한다.^[1]

참조

_[1] 웹사이트 Manhattan distance https://xlinux.nist.[...] 2019-10-06
_[2] 서적 The History of Statistics: The Measurement of Uncertainty before 1900 https://archive.org/[...] Harvard University Press 2019-10-06
_[3] 논문 Untersuchungen über Systeme integrierbarer Funktionen https://zenodo.org/r[...]
_[4] 서적 Geometrie der Zahlen https://archive.org/[...] R. G. Teubner 2019-10-06
_[5] 간행물 You Will Like Geometry. A Guide Book for the Illinois Institute of Technology Geometry Exhibition Museum of Science and Industry
_[6] 서적 Introduction to Calculus Volume II Old Dominion University
_[7] 논문 On the mean value theorem https://doi.org/10.1[...] 1988-01-01
_[8] 간행물 Geometry of some taxicab curves Serbian Society for Geometry and Graphics, University of Niš, Srbija
_[9] 학위논문 Generalizing and Transferring Mathematical Definitions from Euclidean to Taxicab Geometry Georgia State University
_[10] 논문 The Nature of Length, Area, and Volume in Taxicab Geometry https://dergipark.or[...]
_[11] 논문 SAS and SSA Conditions for Congruent Triangles 2018
_[12] 논문 Taxicab Angles and Trigonometry https://www.jstor.or[...] 2000
_[13] 논문 For most large underdetermined systems of linear equations the minimal $\ell_1$ -norm solution is also the sparsest solution 2006-03-23
_[14] 논문 Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes 2011-07-05

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com