보로노이 다이어그램

수치해석 컴퓨터 그래픽스 마지막 수정: 2026-07-12 04:13:51

1. 개요[편집]

보로노이 다이어그램 Voronoi Diagram
정의	가장 가까운 점 기준 공간 분할
쌍대 구조	들로네 삼각분할
대표 알고리즘	포춘의 스윕라인 (O(n log n))
응용	메시 생성, 이웃 탐색, 공간 분석

지도 위에 편의점 위치만 찍어놓고 “각 지점에서 가장 가까운 편의점 구역”을 색칠하면, 그게 바로 보로노이 다이어그램이다.

보로노이 다이어그램(Voronoi diagram)은 평면(또는 공간)에 흩어진 점들의 집합에 대해, 각 점이 “관할하는” 영역으로 공간 전체를 분할한 구조다. 정확히는, 씨앗점(site) $p_i$ 의 보로노이 셀(cell)은 다른 어떤 씨앗점보다 $p_i$ 에 더 가까운 모든 위치의 집합이다.

V(p_i) = \{\, \mathbf{x} : \|\mathbf{x} - p_i\| \le \|\mathbf{x} - p_j\| \;\; \forall j \ne i \,\}

두 씨앗점 사이의 경계는 그 둘을 잇는 선분의 수직이등분선이 되고, 셀들은 서로 겹치지 않는 볼록다각형(2D)이나 볼록다면체(3D)가 되어 공간을 빈틈없이 채운다. 이름은 러시아 수학자 게오르기 보로노이(Georgy Voronoy)에서 왔지만, 개념 자체는 데카르트까지 거슬러 올라가고 후술할 콜레라 사망지도로도 유명하다.¹

단순한 정의에 비해 응용은 놀랄 만큼 넓다. 메시 생성, 입자 시뮬레이션의 이웃 탐색, 로봇 경로 계획, 생태학의 세력권 분석, 심지어 절차적 지형 생성까지 — “가장 가까운 것”을 물어야 하는 모든 문제의 밑바탕에 이 구조가 깔린다.

2. 콜레라 지도와 역사[편집]

보로노이 다이어그램의 가장 유명한 실전 사례는 수학책이 아니라 역학(epidemiology) 역사에 있다. 1854년 런던 콜레라 대유행 당시, 의사 존 스노(John Snow)는 사망자 위치를 지도에 찍고 각 지점이 어느 급수 펌프에 “가장 가까운지”로 구역을 나눴다.² 그 결과 브로드가(街) 펌프의 관할 구역에 사망이 집중되어 있음을 보여, 콜레라가 오염된 물로 전파된다는 사실을 증명했다. 이 펌프 관할 구역 지도가 사실상 손으로 그린 보로노이 다이어그램이다.

수학적 정식화는 이후 디리클레(1850)와 보로노이(1908)의 손을 거쳤다. 그래서 이 구조를 디리클레 테셀레이션(Dirichlet tessellation), 티센 다각형(Thiessen polygon) 등으로도 부른다. 분야마다 이름이 제각각인 것은 그만큼 여러 학문에서 독립적으로 재발견되었다는 방증이다.

3. 들로네 삼각분할과의 쌍대성[편집]

보로노이 다이어그램을 이야기할 때 들로네 삼각분할을 빼놓을 수 없다. 둘은 동전의 양면, 정확히는 쌍대(dual) 관계이기 때문이다.

보로노이 셀이 인접한(경계 모서리를 공유하는) 두 씨앗점을 선분으로 이으면, 그 선분들의 집합이 바로 들로네 삼각분할이 된다.
반대로 들로네 삼각형의 외접원 중심(외심)들이 보로노이 정점(vertex)이 되고, 삼각형 변의 수직이등분선이 보로노이 모서리가 된다.

이 쌍대성은 단순히 예쁜 관계가 아니라 실용적으로 결정적이다. 한쪽을 계산하면 다른 쪽은 사실상 공짜로 얻어지기 때문. 들로네 삼각분할은 “최소 내각을 최대화”(sliver 삼각형 회피)하는 성질 덕에 유한요소 메시 생성에서 선호되는데, 그 품질 보증의 이론적 근거가 보로노이 구조의 기하다.³ 실무 코드는 보통 들로네를 먼저 구성하고 필요할 때 보로노이를 유도하는 방식을 쓴다.

4. 포춘 알고리즘[편집]

$n$ 개의 씨앗점에 대해 보로노이 다이어그램을 만드는 나이브한 방법은 모든 점쌍의 수직이등분선을 구해 교차시키는 것이지만, 이는 $O(n^2 \log n)$ 이상으로 느리다. 이 문제를 최적 복잡도로 해결한 것이 1986년 스티븐 포춘(Steven Fortune)의 스윕라인 알고리즘이다.⁴

포춘 알고리즘의 아이디어는 수평선(sweep line)을 위에서 아래로 훑으면서, 이미 지나간 씨앗점들이 만드는 포물선 호(arc)들의 경계선인 “해안선(beach line)“을 유지하는 것이다. 스윕라인이 새 씨앗점을 만나면 해안선에 새 포물선이 끼어들고(site event), 포물선 호가 사라지는 순간(circle event)에 보로노이 정점이 확정된다. 이벤트를 우선순위 큐로 관리하며, 전체 시간복잡도는 다음과 같다.

O(n \log n)

이는 비교 기반 알고리즘의 이론적 하한과 일치하는 최적 복잡도다. 다른 접근으로는 분할정복법, 그리고 들로네를 점진적으로 구성하는 증분 삽입법(Bowyer-Watson)이 있는데, 특히 후자는 구현이 단순해 실무에서 널리 쓰인다.

5. 시뮬레이션에서의 응용[편집]

보로노이 구조는 계산과학·그래픽스 전반에서 조용히 일하고 있다.

메시 생성과 격자: 들로네-보로노이 쌍은 비정형 격자 생성의 표준 도구다. 나아가 각 셀을 그 무게중심으로 반복 이동시키는 로이드 완화(Lloyd relaxation)로 균질한 중심 보로노이 테셀레이션(CVT)을 만들면, 유한체적법에 이상적인 고른 격자가 나온다.
이웃 탐색: SPH나 입자 기반 유동에서 각 입자의 상호작용 이웃을 찾는 문제는 본질적으로 근접 질의(proximity query)다. 보로노이 셀 구조나 그와 밀접한 공간 분할 자료구조(k-d 트리, 셀 리스트)로 가속한다.
자연 이웃 보간: 시블슨(Sibson) 보간은 보로노이 셀 면적의 변화량을 가중치로 삼아 산포 데이터를 부드럽게 보간한다. 보간과 근사의 한 갈래.
컴퓨터 그래픽스: 절차적 텍스처(셀룰러 노이즈, 웨어리 노이즈), 균열·파쇄 시뮬레이션, 점묘(stippling), 세력권 지도 등. 레이 트레이싱 가속 구조와도 인접하다.

한 마디로 “가장 가까운 것을 빠르게 찾아라”라는 요구가 있는 곳이면, 그 뒤편엔 거의 항상 보로노이 다이어그램의 그림자가 있다. 편의점 상권 분석부터 우주 대규모 구조의 은하 분포 분석까지 스케일을 넘나드는, 의외로 만능인 도구다.

6. 관련 문서[편집]

데카르트는 1644년 저서에서 태양계 물질 분포를 비슷한 방식으로 나눈 그림을 남겼다. 다들 자기 분야에서 재발견해놓고 이름은 보로노이가 다 가져간 셈. 억울한 디리클레와 티센을 위해 묵념. ↩
스노는 지도에 펌프까지의 도보 거리 경계까지 손으로 그렸는데, 단순 직선거리가 아니라 실제 걸어가는 길을 반영한 “가중 보로노이”에 가까웠다. 150년 전에 이미 응용까지 앞서갔던 셈이다. ↩
들로네 삼각분할은 “빈 외접원 성질(empty circumcircle property)“을 만족한다. 어떤 삼각형의 외접원 내부에도 다른 점이 없다는 것인데, 이게 바로 보로노이 정점의 정의와 정확히 대응한다. 쌍대성이 기하학적으로 드러나는 지점. ↩
Fortune, S. (1987). A sweepline algorithm for Voronoi diagrams. 스윕라인이 지나갈 때 포물선 해안선이 넘실대는 애니메이션은 알고리즘 강의의 단골 볼거리다. 처음 보면 “이걸 대체 어떻게 생각해냈지” 싶은 우아함이 있다. ↩