맨해튼 거리

맨해튼 거리와 유클리드 거리의 비교: 빨간색, 파란색, 노란색 선은 길이가 12로 같으며, 유클리드 거리와 맨해튼 거리 양쪽 모두 가지고 있다. 유클리드 기하학의 경우 초록색 선의 길이는 6×√2 ≈ 8.48로, 선들 가운데 유일하게 길이가 가장 짧으며, 맨해튼 거리의 경우 초록색 선의 길이는 12로, 이보다 길이가 더 짧은 선은 없다.

맨해튼 거리(Manhattan distance, 혹은 택시 거리, L₁ 거리, 시가지 거리)는 19세기의 수학자 헤르만 민코프스키가 고안한 용어로, 보통 유클리드 기하학의 거리공간을 좌표에 표시된 두 점 사이의 거리(절대값)의 차이에 따른 새로운 거리공간으로 대신하기도 한다.

정의

맨해튼 거리는 $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}|$이면

$\mathbf {p} =(p_{1},p_{2},\dots ,p_{n})\,$과 $\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})\,$는 공간 벡터가 된다.

예를 들어 평면 위의 맨해튼 거리가 $(p_{1},p_{2})$과 $(q_{1},q_{2})$ 사이이면 $|p_{1}-q_{1}|+|p_{2}-q_{2}|$이다. 맨해튼 거리는 좌표계의 회전에 의존하지만, 좌표의 축을 반사하거나 평행이동을 하는 경우는 그렇지 않다. 맨해튼 거리는 SAS 합동 (두 개의 변과 그 사이의 각이 같은 두 개의 삼각형을 만들 수 있으나, 합동이 아니다.)인 경우를 제외하면 모든 힐베르트 공리계 (유클리드 기하학의 의식화)와 일치한다.

원은 일정한 거리에 있는 점을 반지름이라고 부르며, 점에서부터는 중심으로 부른다. 거리를 통해 결정되는 유클리드 기하학에 비해 맨해튼 거리는 원의 모양도 다르다. 맨해튼 거리에서 원은 정사각형에서 좌표의 축으로 45° 방향에 있다. 모눈의 크기가 줄어들면 수많은 점들은 정사각형의 연속적인 맨해튼 거리 회전을 하는데, 유클리드 거리를 이용한 각 변이 길이가 √2r이면 반지름 r에서 맨해튼 거리의 길이는 2r이 된다.

원의 반지름이자 체비셰프 거리 (Lp 거리)인 r은 정사각형 평면에 평행하며, 정사각형의 변의 길이인 2r은 좌표의 축에 평행하다. 평면의 체비셰프 거리는 거리의 회전과 축소된 평면의 맨해튼 거리와 같은 값이지만, L₁과 L_∞의 거리 사이의 같은 값은 보다 높은 차원에서 일반화되지 않고 있다.

체스에서의 측정

체스에서는 룩을 위한 체스판과 정사각형 사이의 거리를 맨해튼 거리로 측정하는데, 킹과 퀸은 체비셰프 거리를 이용하며, 비숍은 체스판을 45도로 순환하는 맨해튼 거리 (같은 색의 정사각형)를 이용한다. 즉, 대각선 방향의 축의 좌표이다. 하나의 칸에 따로 도달하기 위해서는 하나뿐인 킹과 같은 거리에 있는 룩과 퀸, 비숍 1개나 2개를 옮겨야 한다. (비어 있는 체스판에 모든 비숍을 옮길 수 있는 상황이다고 가정한다.)

주석

• Eugene F. Krause. 《Taxicab Geometry》. Dover. ISBN 0-486-25202-7. 

바깥 고리

• City Block Distance, 카르디 테크노모
• city-block metric 플래닛매스
• 택시 거리
• Manhattan distance. Paul E. Black, Dictionary of Algorithms and Data Structures, NIST
• 택시기하학