맨해튼 거리

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

정의

맨해튼 거리는 $d_{1}$ 과 벡터 $\mathbf {p} ,\mathbf {q}$ 사이에 차원 실수를 데카르트 좌표계에 일정한 좌표축의 점 위에 투영한 선분 길이의 합을 말하는데, 이를 공식으로 표현하면 다음과 같다.

$\mathbf {p} =(p_{1},p_{2},\dots ,p_{n})\,$ 과 $\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})\,$ 를 공간 벡터라 할 때,

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

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

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

체스에서의 측정

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

같이 보기

각주

Eugene F. Krause (1987). 《Taxicab Geometry》. Dover. ISBN 0-486-25202-7.

외부 링크

City Block Distance, 카르디 테크노모
city-block metric Archived 2007년 7월 1일 - 웨이백 머신 플래닛매스(PlanetMath)
택시 거리
Manhattan distance. Paul E. Black, Dictionary of Algorithms and Data Structures, NIST
택시기하학