보로노이 다이어그램(Voronoi diagram)

도시에 우체국이 몇 곳 있다고 합시다. 집집마다 가장 가까운 우체국에 맡기면 도시가 조각으로 나뉩니다. 이렇게 평면을 가장 가까운 기준점별로 나눈 지도가 보로노이 다이어그램이고, 조각 하나를 보로노이 영역(세포)이라고 부릅니다. 이름은 이 분할을 연구한 러시아 제국의 수학자 게오르기 보로노이에게서 왔습니다. '가장 가깝다'는 말에는 거리 함수⁠(metric)⁠가 필요하니, 거리를 바꾸면 지도도 바뀝니다.

거리는 , 기준점은 개입니다. 기준점을 끌어 보세요. 흰검은 고리 Q는 영역에 있고, 가장 가까운 기준점까지 입니다. 그 영역은 전체 넓이⁠(area)⁠의 를 차지합니다. 새 기준점 영역의 무게중심으로 옮기기

유클리드 거리⁠(Euclidean distance)⁠에서 두 기준점 a, b까지의 거리가 같은 점들은 선분 ab의 수직이등분선입니다. $|x - a|^2 = |x - b|^2$을 풀어 보면 $|x|^2$ 항이 지워지고 일차식 $2\,x\cdot(b - a) = |b|^2 - |a|^2$만 남기 때문입니다(내적⁠, dot product⁠). 그러니 a의 영역은 'b보다 a에 가까운 쪽'이라는 반평면들을 모든 b에 대해 겹친 부분입니다. 반평면을 겹친 모양은 안쪽으로 파인 곳이 없으니 영역은 모두 볼록합니다. 기준점들을 둘러싼 가장 작은 볼록다각형⁠(convex polygon)⁠의 꼭짓점⁠(vertex)⁠에 놓인 기준점들의 영역은 한쪽으로 끝없이 뻗고, 나머지는 사방이 막힌 볼록다각형입니다. 세 영역이 만나는 꼭짓점은 세 기준점에서 같은 거리에 있으니 세 기준점을 지나는 원의 중심입니다. Q 둘레의 흰검은 곡선은 가장 가까운 기준점까지를 반지름으로 한 '원'입니다. 그 안에는 다른 기준점이 하나도 없습니다.

거리를 맨해튼 거리⁠(Manhattan distance)⁠나 체비쇼프 거리⁠(Chebyshev distance)⁠로 바꾸면 경계가 가로세로와 45° 선분으로 꺾입니다. 모든 기준점에서 같은 속도⁠(velocity)⁠로 그 거리의 '원'(마름모, 정사각형)을 부풀릴 때 먼저 닿은 쪽이 땅을 차지한다고 생각하면 됩니다. 경계의 모양이 Lp 노름⁠(Lp norm)⁠의 단위원⁠(unit circle)⁠을 닮는 까닭입니다. 이 두 거리에서는 거리가 똑같은 곳이 선이 아니라 넓은 면이 되기도 합니다(회색). 맨해튼 거리에서는 두 기준점이 정확히 45° 대각선 방향에 있을 때(가로 차와 세로 차가 같을 때), 체비쇼프 거리에서는 두 기준점이 가로나 세로로 나란할 때 그렇습니다. 이런 면을 어느 쪽에 줄지는 따로 약속해야 합니다. 넓이의 몫은 칸을 세어 구했는데, 칸을 잘게 할수록 참값에 다가가는 리만 합⁠(Riemann sum)⁠과 같은 생각입니다.

새 점을 분류할 때 가장 가까운 예의 이름표를 붙이는 최근접 이웃 분류(k = 1)는 보로노이 영역⁠(Voronoi region)⁠에 이름표를 붙이는 것과 같습니다. 영역 안의 점은 모두 그 기준점이 가장 가까우니까요. '무게중심으로 옮기기'를 여러 번 눌러 보세요. 점마다 가장 가까운 중심에 배정하고(보로노이 영역) 중심을 영역의 무게중심으로 옮기기를 되풀이하는 것은 k-평균 군집⁠(k-means clustering)⁠을 푸는 로이드 알고리즘입니다(1957년 벨 연구소의 스튜어트 로이드가 제안). 무게중심은 영역 안 점들까지의 유클리드 거리 제곱의 합을 가장 작게 하는 점이라, 한 번 옮길 때마다 그 합이 줄어들거나 그대로입니다. 되풀이하면 영역들이 고르게 퍼집니다. 다만 도착하는 배치는 출발점에 따라 다르고, 가장 좋은 배치라는 보장은 없습니다. 맨해튼 거리를 골랐을 때 이 합을 줄이려면 무게중심 대신 좌표별 중앙값⁠(median)⁠으로 옮겨야 합니다.

이어지는 곳.

• 곧은 거리 대신 도로를 따라 재면 그래프의 최단 경로⁠(shortest path)⁠ 거리로 나눈 보로노이가 됩니다. 불이 났을 때 어느 소방서가 가장 빨리 닿는지 정하는 지도입니다.
• 지구 전체라면 대원⁠(great circle)⁠을 따른 측지선⁠(geodesic)⁠ 거리로 구면을 나눕니다(구면기하⁠, spherical geometry⁠).
• 비트열을 해밍 거리⁠(Hamming distance)⁠로 나눈 영역은 오류 정정 부호⁠(error-correcting code)⁠의 해독 규칙입니다. 받은 비트열을 가장 가까운 부호어⁠(codeword)⁠로 읽기 때문입니다.
• 연속적인 신호 값을 몇 단계의 대표값으로 줄이는 양자화기⁠(quantizer)⁠는 값마다 가장 가까운 대표값으로 반올림합니다. 그러니 그 칸은 대표값들로 수직선을 나눈 1차원 보로노이 칸이고, 대표값을 잘 고르는 문제가 율–왜곡 이론⁠(rate–distortion theory)⁠으로 이어집니다.
• 수억 개의 문서 벡터⁠(vector)⁠를 k-평균⁠(mean)⁠으로 묶어 두고 질문과 가까운 묶음 안에서만 찾는 역색인⁠(inverted file index)⁠은 중심점들의 보로노이 다이어그램을 쓰는 것입니다(검색 증강 생성⁠(retrieval-augmented generation)⁠). 내적 점수가 가장 큰 전문가를 고르는 전문가 혼합⁠(mixture of experts)⁠의 라우터⁠(router)⁠도 입력 공간을 이와 닮은 볼록한 영역들로 나눕니다.
• 유클리드 거리에서 영역이 변을 맞댄 기준점끼리 선분으로 이으면, 기준점들을 둘러싼 가장 작은 볼록다각형의 안쪽이 삼각형들로 나뉩니다(네 기준점이 한 원 위에 놓이는 특별한 경우만 빼면). 1934년 러시아 수학자 보리스 들로네가 연구해 들로네 삼각분할⁠(Delaunay triangulation)⁠이라 합니다. 여기에는 모든 기준점을 가장 짧은 선분들로 잇는 최소 신장 트리⁠(minimum spanning tree)⁠가 언제나 들어 있어서, 트리⁠(tree)⁠를 찾을 때 모든 쌍 대신 이 선분들만 보면 됩니다.
• 기준점마다 가중치⁠(weight)⁠를 주어 무거운 기준점이 더 넓은 땅을 갖게 하면 파워 다이어그램⁠(power diagram)⁠이 됩니다. 한 분포를 정해진 몫만큼 여러 점에 나누어 옮기는 최적 수송⁠(optimal transport)⁠ 문제의 답이 이런 모양입니다.
• 평면을 이렇게 겹치지 않는 조각들로 나누는 일(분할)은 1850년 디리클레, 1908년 보로노이가 연구했습니다. 1854년 런던 콜레라 때 존 스노가 집마다 가장 가까운 우물을 기준으로 동네를 나눠 본 지도가 이른 예로 자주 꼽힙니다.