맨해튼 거리(Manhattan distance)

뉴욕 맨해튼처럼 길이 바둑판 모양인 도시에서 택시는 건물을 뚫고 갈 수 없습니다. 가로로 $|\Delta x|$블록, 세로로 $|\Delta y|$블록을 가야 하니 달린 거리는 둘의 합입니다. 이것이 맨해튼 거리(택시 거리)입니다. 새가 날아가는 곧은 거리, 곧 피타고라스 정리⁠(Pythagorean theorem)⁠의 빗변⁠(hypotenuse)⁠인 유클리드 거리⁠(Euclidean distance)⁠보다 늘 길거나 같습니다.

출발점 P와 도착점 Q를 교차로 사이에서 끌어 보세요. 택시 거리는 블록, 곧은 거리는 블록이고, 비는 입니다. 이 비는 1(한 방향으로만 갈 때)과 $\sqrt 2$(정확히 대각선 방향일 때) 사이에 있습니다.

가장 짧은 택시 길은 하나가 아닙니다. 오른쪽으로 번, 위로 번 가는 순서만 정하면 되니, 그 개수는 이항계수⁠(binomial coefficient)⁠ 입니다. 다른 최단 경로 교차로마다 적힌 수는 바로 아래 교차로와 바로 왼쪽 교차로의 수를 더한 값입니다(그곳에 도착하는 마지막 한 걸음이 둘 중 하나이므로). 그래서 수들이 비스듬히 누운 파스칼의 삼각형⁠(Pascal's triangle)⁠을 이룹니다. 도로망을 그래프로 보면 맨해튼 거리는 그 그래프 위의 최단 경로⁠(shortest path)⁠ 길이입니다.

한 점에서 택시 거리가 $r =$ 인 점들을 모으면 원이 아니라 45° 기울어진 정사각형(마름모)이 됩니다. 그 위의 교차로는 개($4r$개)입니다. 이 '원'의 둘레를 택시 거리로 재면 , 지름은 이니 이 기하⁠(geometry)⁠에서 원주율⁠(pi)⁠은 4입니다.

맨해튼 거리는 좌표마다 따로 계산해 더할 뿐입니다. 그래서 여러 집에서 잰 택시 거리의 합이 가장 작은 모임 장소는 x좌표들의 중앙값⁠(median)⁠과 y좌표들의 중앙값으로 된 점입니다. 평균⁠(mean)⁠이 아닙니다. 한 줄로 늘어선 집들을 생각하면 이유가 보입니다. 모임 장소를 한쪽으로 조금 옮기면, 그쪽에 있는 집들과는 가까워지고 반대쪽 집들과는 그만큼 멀어집니다. 중앙값에서는 양쪽 집의 수가 같으니 어느 쪽으로 옮겨도 합이 줄지 않습니다. 집이 짝수 채이면 가운데 두 집 사이의 어느 점이든 똑같이 최선입니다. 예를 들어 집이 0, 1, 10에 있으면 중앙값 1에서 합은 1 + 0 + 9 = 10이고, 평균 11/3 ≈ 3.67에서는 38/3 ≈ 12.67입니다.

제곱 거리의 합을 줄이면 중앙값 대신 평균이 나오고, 그것이 최소제곱법⁠(method of least squares)⁠의 선형 회귀입니다. 절댓값⁠(absolute value)⁠의 합을 줄이는 회귀는 멀리 튄 값에 덜 휘둘립니다. 대신 절댓값 그래프는 0에서 뾰족하게 꺾여 미분⁠(differentiation)⁠할 수 없는 점이 있으니 최적화⁠(optimization)⁠가 조금 까다롭습니다. 성분의 절댓값 합은 벡터⁠(vector)⁠의 크기를 재는 한 방법, 곧 p = 1인 Lp 노름⁠(Lp norm)⁠입니다.

이어지는 곳. 이 거리도 세 규칙을 지키는 거리 함수⁠(metric)⁠입니다.

• 0과 1로 된 벡터 사이에서는 성분마다의 차이 $|\Delta|$가 같으면 0, 다르면 1이니, 맨해튼 거리는 서로 다른 자리의 개수, 곧 해밍 거리⁠(Hamming distance)⁠입니다.
• 가로와 세로로 동시에 한 칸씩 움직일 수 있으면 체비쇼프 거리⁠(Chebyshev distance)⁠가 됩니다. 평면에서는 둘이 45° 돌린 관계라서, 좌표를 45° 돌리고 늘이면 한 거리가 다른 거리로 바뀝니다.
• 택시 거리로 그린 보로노이 다이어그램⁠(Voronoi diagram)⁠은 경계가 45°로 꺾입니다. 이 거리의 '원'이 마름모이기 때문입니다.
• 이런 거리는 19세기 말 독일 수학자 헤르만 민코프스키가 다룬 여러 거리 가운데 하나였고, '택시 기하학⁠(taxicab geometry)⁠'이라는 이름은 20세기 중반에 흔히 쓰이기 시작했습니다.
• 두 거리 공간⁠(metric space)⁠을 곱해 좌표 쌍의 공간을 만들 때, 좌표 거리를 어떻게 합칠지는 두 가지가 자연스럽습니다. 최댓값(체비쇼프)을 쓰면 범주론⁠(category theory)⁠의 곱이 되고, 합(맨해튼)을 쓰면 '두 변수 함수⁠(function)⁠를 한 변수씩 차례로 받는 함수로 바꾸기'(커링⁠, currying⁠)가 되는 곱, 곧 텐서곱⁠(tensor product)⁠이 됩니다. 여기서 화살표는 거리를 늘리지 않는 사상입니다. 이 차이는 풍부화된 범주⁠(enriched category)⁠의 틀에서 드러납니다.