보로노이 다이어그램

1. 개요

보로노이 다이어그램은 거리 공간에서 정의되는 기하학적 구조로, 주어진 점 집합을 기반으로 공간을 분할한다. 각 점(사이트)에 대해, 해당 사이트까지의 거리가 다른 사이트보다 가깝거나 같은 공간의 영역(보로노이 셀)을 정의하며, 이 셀들의 집합을 보로노이 다이어그램이라고 한다. 보로노이 다이어그램은 유클리드 평면, 쌍대 그래프, 들로네 삼각 분할, 다양한 거리 함수를 사용하는 일반적인 정의를 갖는다. 생물학, 수문학, 로봇 공학, 컴퓨터 그래픽스 등 다양한 분야에서 활용되며, 최근접 탐색, 경로 계획, 데이터 구조 구축, 이미지 처리 등에 응용된다.

2. 정의

보로노이 다이어그램은 거리 공간에서 주어진 특별한 점 또는 부분 집합(이를 사이트(site) 또는 모점(generator)이라고 한다)들에 대해, 각 사이트에 가장 가까운 점들의 집합으로 공간을 분할하는 방식이다. 각 사이트에 가장 가까운 점들의 집합을 보로노이 셀(Voronoi cell) 또는 보로노이 영역(Voronoi region)이라고 하며, 이 셀(영역)들의 전체 모음을 보로노이 다이어그램(Voronoi diagram)이라고 부른다.

가장 간단한 예는 유클리드 평면 위에 여러 개의 점(사이트)이 주어졌을 때, 각 점에 가장 가까운 영역으로 평면을 나누는 것이다. 이 경우 각 보로노이 셀은 볼록 다각형 형태를 띤다. 하지만 보로노이 다이어그램은 더 일반적인 거리 공간과 다양한 형태의 사이트에 대해서도 정의될 수 있으며, 사용되는 거리 함수에 따라 다이어그램의 모습이 달라진다.

2.1. 기본 개념

가장 단순한 경우로, 유클리드 평면에 있는 유한한 점들의 집합 $\backslash \{p\_1,\backslash dots\; p\_n\backslash \}$을 생각해 볼 수 있다. 이 점들을 사이트(site) 또는 모점(generator)이라고 부른다. 각 사이트 $p\_k$에 대해, 해당 보로노이 셀(Voronoi cell) $R\_k$는 평면 위의 점들 중에서 $p\_k$가 가장 가까운 사이트인 점들의 집합으로 정의된다. 즉, 어떤 점 $x$가 셀 $R\_k$에 속한다는 것은 $x$와 $p\_k$ 사이의 거리가 다른 어떤 사이트 $p\_j$ ($j\; \backslash neq\; k$)와의 거리보다 작거나 같다는 의미이다 ($d(x,\; p\_k)\; \backslash le\; d(x,\; p\_j)$).

어떤 두 사이트 $p\_j$와 $p\_k$에 대해, $p\_k$에 더 가깝거나 거리가 같은 점들의 집합은 두 점을 잇는 선분 $p\_jp\_k$의 수직 이등분선을 경계로 하는 닫힌 반공간을 형성한다. 보로노이 셀 $R\_k$는 이러한 $n-1$개의 닫힌 반공간들의 교집합으로 정의되므로, 항상 볼록 다각형 형태를 띤다.

보로노이 다이어그램에서 두 셀이 만나는 경계는 두 개의 가장 가까운 사이트로부터 같은 거리에 있는 점들의 집합이며, 이는 선분, 반직선, 또는 선이 될 수 있다. 세 개 이상의 경계가 만나는 다이어그램의 꼭짓점은 세 개 이상의 사이트로부터 같은 거리에 있는 점을 나타낸다.

간단한 예로, 도시 안에 여러 개의 상점이 있다고 가정해 보자. 특정 상점을 이용하는 고객 수를 추정하고 싶을 때, 다른 조건(가격, 서비스 등)이 동일하다면 고객들은 가장 가까운 상점을 선택할 것이라고 가정할 수 있다. 이 경우, 각 상점 $P\_k$의 보로노이 셀 $R\_k$는 그 상점을 이용할 가능성이 있는 잠재 고객들의 지리적 범위를 나타내는 근사치로 사용될 수 있다.

대부분의 도시에서 점 사이의 거리는 일반적으로 유클리드 거리를 사용하여 측정한다.
:$\backslash ell\_2\; =\; d\backslash left[\backslash left(a\_1,\; a\_2\backslash right),\; \backslash left(b\_1,\; b\_2\backslash right)\backslash right]\; =\; \backslash sqrt\{\backslash left(a\_1\; -\; b\_1\backslash right)^2\; +\; \backslash left(a\_2\; -\; b\_2\backslash right)^2\}$
또는 경우에 따라 맨해튼 거리를 사용할 수도 있다.
:$d\backslash left[\backslash left(a\_1,\; a\_2\backslash right),\; \backslash left(b\_1,\; b\_2\backslash right)\backslash right]\; =\; \backslash left|a\_1\; -\; b\_1\backslash right|\; +\; \backslash left|a\_2\; -\; b\_2\backslash right|$.
어떤 거리 측정법을 사용하느냐에 따라 생성되는 보로노이 다이어그램의 모양은 달라진다.

--
--

더 일반적으로, 거리 공간 $(X,\; d)$ 내의 유한 집합인 부분 집합 $P\; \backslash subset\; X$가 주어졌을 때, 각 점 $p\; \backslash in\; P$를 모점 또는 사이트라고 부른다. 이에 대해 $X$ 내에서 "$P$의 점들 중에서 $p$가 가장 가깝다"는 점들의 집합, 즉
: $V(p)\; =\; \backslash \{x\; \backslash in\; X\; \backslash mid\; \backslash forall\; q\; \backslash in\; P\; \backslash ;\; [d(x,\; p)\; \backslash le\; d(x,\; q)]\backslash \}$
를 $p$의 보로노이 영역(Voronoi region)이라고 부른다. $P$의 모든 점들의 영역들을 모은 집합(과 이들이 유도하는 셀 복합체)을 보로노이 다이어그램(Voronoi diagram)이라고 부른다.

보로노이 영역의 경계를 보로노이 경계(Voronoi edge), 각 보로노이 경계의 교점을 보로노이 점(Voronoi vertex)이라고 부른다.

2.2. 일반적인 정의

가장 단순한 경우, 유클리드 평면에 있는 유한한 점들의 집합 $\backslash \{p\_1,\backslash dots\; p\_n\backslash \}$이 주어졌다고 가정해보자. 이 경우 각 사이트(site) $p\_k$는 주어진 점 중 하나이며, 해당 보로노이 셀(Voronoi cell) $R\_k$는 유클리드 평면 위의 모든 점들 중에서 $p\_k$에 가장 가까운 점들의 집합이다. 즉, 어떤 점 $x$가 $R\_k$에 속한다는 것은 $x$에서 $p\_k$까지의 거리가 다른 어떤 사이트 $p\_j$ ($j\; \backslash neq\; k$)까지의 거리보다 작거나 같다는 의미이다.

점 $x$가 $p\_k$에 더 가깝거나 거리가 같은 점들의 집합은, $p\_k$와 다른 사이트 $p\_j$를 잇는 선분의 수직 이등분선을 경계로 하는 닫힌 반공간을 형성한다. 따라서 셀 $R\_k$는 이러한 모든 반공간들의 교집합으로 정의되며, 그 결과 볼록 다각형이 된다. 보로노이 다이어그램에서 두 셀의 경계는 두 개의 가장 가까운 사이트로부터 같은 거리에 있는 점들의 집합으로, 이는 선분, 반직선, 또는 선이 될 수 있다. 세 개 이상의 경계가 만나는 다이어그램의 꼭짓점은 세 개 이상의 사이트로부터 동일한 거리에 있는 점이다.

보로노이 다이어그램의 개념은 더 일반적으로 거리 함수 $d$가 정의된 거리 공간 $X$로 확장될 수 있다. $K$를 인덱스 집합이라 하고, $(P\_k)\_\{k\; \backslash in\; K\}$를 공간 $X$ 내의 비어 있지 않은 부분 집합(사이트)들의 튜플(순서가 있는 모음)이라고 하자. 사이트 $P\_k$에 해당하는 보로노이 셀 또는 보로노이 영역 $R\_k$는 $X$ 안의 모든 점 $x$ 중에서, $P\_k$까지의 거리 $d(x,\; P\_k)$가 다른 어떤 사이트 $P\_j$ ($j\; \backslash neq\; k$)까지의 거리 $d(x,\; P\_j)$보다 작거나 같은 점들의 집합이다. 여기서 점 $x$와 부분 집합 $A$ 사이의 거리는 $d(x,\backslash ,\; A)\; =\; \backslash inf\backslash \{d(x,\backslash ,\; a)\; \backslash mid\; a\; \backslash in\; A\backslash \}$로 정의된다. 즉,
$$R\_k\; =\; \backslash \{x\; \backslash in\; X\; \backslash mid\; d(x,\; P\_k)\; \backslash leq\; d(x,\; P\_j)\backslash ;\; \backslash text\{for\; all\}\backslash ;\; j\; \backslash neq\; k\backslash \}$$
보로노이 다이어그램(Voronoi diagram)은 이러한 셀들의 튜플 $(R\_k)\_\{k\; \backslash in\; K\}$ 전체를 의미한다. 사이트들은 서로 교차하거나 겹칠 수도 있지만, 보통은 서로 떨어져 있다고 가정한다. 무한히 많은 사이트가 정의에 포함될 수도 있지만(이는 수의 기하학이나 결정학 등에서 활용된다), 많은 경우 유한 개의 사이트만 고려한다.

공간이 유한 차원 유클리드 공간이고, 각 사이트가 점이며, 유한 개의 서로 다른 점들이 주어졌다면, 보로노이 셀은 볼록 다면체가 된다. 이 경우 보로노이 다이어그램은 꼭짓점, 모서리, 면 등의 조합적 구조로 표현될 수 있다. 하지만 일반적인 경우에는 보로노이 셀이 볼록하지 않거나 연결되어 있지 않을 수도 있다.

요약하자면, 거리 공간 $(X,\; d)$ 내의 유한 집합인 부분 집합 $P\; \backslash subset\; X$가 주어졌을 때, 각 점 $p\; \backslash in\; P$를 모점 또는 사이트라고 부른다. 각 사이트 $p$에 대해, $P$의 점들 중에서 $p$가 가장 가까운 $X$ 내의 점들의 집합
: $V(p)\; =\; \backslash \{x\; \backslash in\; X\; \backslash mid\; \backslash forall\; q\; \backslash in\; P\; \backslash ;\; [d(x,\; p)\; \backslash le\; d(x,\; q)]\backslash \}$
을 $p$의 (보로노이) 영역이라고 하며, $P$의 모든 점들의 영역들을 모은 집합(또는 이들이 이루는 셀 복합체)을 보로노이 다이어그램이라고 부른다.

보로노이 영역의 경계를 보로노이 경계라고 하며, 각 보로노이 경계가 만나는 점을 보로노이 점이라고 부른다. Tran 등의 표현에 따르면, "보로노이 다각형 내의 모든 위치는 유클리드 평면의 보로노이 다이어그램에서 다른 모든 생성 점보다 해당 다각형의 생성 점에 더 가깝다".

3. 성질

보로노이 다이어그램과 보로노이 영역(셀)은 다음과 같은 특징을 갖는다.

* 각 보로노이 영역은 볼록 집합이다.
* 보로노이 영역의 경계에 있는 점(보로노이 점)은 해당 경계를 정의하는 두 개 이상의 모점(사이트)으로부터 같은 거리에 위치한다. 특히 2차원 유클리드 평면의 경우, 이는 모점들을 중심으로 하는 원들의 교점이 된다.
* 보로노이 다이어그램의 쌍대 그래프 (점 사이트를 갖는 유클리드 공간의 경우)는 동일한 점 집합에 대한 들로네 삼각 분할과 같다.
* 최근접 점 쌍은 보로노이 다이어그램에서 서로 인접한 두 개의 셀에 해당한다.
* 유클리드 평면에 이산적인 점 집합이 주어졌다고 가정하면, 집합 내 두 점이 볼록 껍질에서 인접하는 경우는 해당 보로노이 셀들이 무한히 긴 변을 공유할 때뿐이다.
* 공간이 노름 공간이고 각 사이트까지의 거리가 정의되는 경우 (예: 사이트가 콤팩트 집합 또는 닫힌 공인 경우), 각 보로노이 셀은 사이트에서 뻗어 나가는 선분들의 합집합으로 나타낼 수 있다. 거리가 정의되지 않으면 이 속성이 반드시 성립하지는 않는다.
* 비교적 일반적인 조건 하에서 (공간이 무한 차원의 균등 볼록 공간일 수 있고, 일반적인 형태의 무한히 많은 사이트가 있을 수 있는 등) 보로노이 셀은 기하학적 안정성이라는 특정 안정성 속성을 갖는다. 즉, 사이트의 모양에 작은 변화(예: 변환이나 왜곡)가 생기면 보로노이 셀의 모양에도 작은 변화만 발생한다. 그러나 공간이 2차원이지만 균등 볼록 공간이 아니거나(특히 비 유클리드 공간), 사이트가 점인 경우에는 이 안정성이 일반적으로 성립하지 않는다.

4. 역사

보로노이 다이어그램의 개념은 비공식적으로 1644년 르네 데카르트의 연구까지 거슬러 올라간다. 1850년에는 페터 구스타프 르줜 디리클레가 이차 형식 연구에서 2차원 및 3차원 보로노이 다이어그램을 사용했다. 이 때문에 보로노이 다이어그램은 '디리클레 테셀레이션'이라는 이름으로도 불린다.

영국의 의사 존 스노우는 1854년 런던에서 발생한 브로드 스트리트 콜레라 발병 당시, 보로노이 다이어그램과 유사한 방식을 활용했다. 그는 특정 브로드 스트리트 펌프 주변에 사는 사람들이 다른 펌프 주변 거주자들보다 콜레라로 더 많이 사망했다는 사실을 밝혀내어, 감염 원인을 규명하는 데 기여했다.

보로노이 다이어그램이라는 이름은 러시아의 수학자 게오르기 표도로비치 보로노이에서 유래했다. 그는 1908년에 일반적인 n차원 공간에서의 보로노이 다이어그램을 정의하고 연구하여 개념을 일반화했다.

지구물리학이나 기상학 분야에서는 공간적으로 분포된 데이터를 분석하기 위해 보로노이 다이어그램을 사용하는데, 특히 1911년 미국의 기상학자 알프레드 H. 티센이 흩어진 측정 지점들로부터 평균 강수량을 추정하기 위해 이 방법을 사용한 이후 '티센 다각형'이라고도 불린다. 이 외에도 분야에 따라 응집 물질 물리학에서는 '위그너-자이츠 단위 셀', 운동량의 역격자에서는 '브릴루앙 영역', 리 군의 일반 격자에서는 '기본 영역', 일반 거리 공간에서는 '계량 기본 다각형' 등 다양한 이름으로 불린다.

5. 응용 분야

보로노이 다이어그램은 점들의 집합으로부터 공간을 분할하는 기하학적 구조로, 다양한 분야에서 문제 해결을 위한 강력한 도구로 사용된다. 특히 공간 분석 및 모델링에 유용하며, 특정 지점이나 개체에 가장 가까운 영역을 정의하는 데 효과적이다.

기하학에서는 점 집합 내에서 가장 큰 빈 원을 찾거나, 객체의 둥근 정도를 계산하는 등 다양한 기하학적 문제를 해결하는 데 활용된다. 예를 들어, 기존 상점들로부터 최대한 멀리 떨어진 곳에 새로운 상점을 배치하는 문제를 해결하는 데 응용될 수 있다.

데이터 구조 분야에서는 점 위치 문제를 해결하고 최근접 이웃 탐색 쿼리에 효율적으로 응답하는 데 사용된다. 이는 특정 지점에서 가장 가까운 병원이나 시설을 찾거나, 데이터베이스에서 가장 유사한 항목을 검색하는 데 유용하다. 또한, 데이터 압축에 사용되는 벡터 양자화와 같은 대규모 응용 분야의 기반이 되기도 한다.

이 외에도 보로노이 다이어그램은 과학, 공학, 정보 과학, 사회 과학 등 수많은 분야에서 특정 문제 상황에 맞게 변형되어 활용되고 있다. 각 분야에서의 구체적인 응용 사례는 아래 하위 섹션에서 자세히 다룬다.

5.1. 과학

보로노이 다이어그램은 다양한 과학 분야에서 활용된다.

* 기상학 및 수문학: 특정 지역 내 강수량 자료에 대한 가중치를 구하는 데 사용된다. 강수량 관측소를 점으로 사용하여 보로노이 다이어그램을 생성하는데, 이를 티센 다각형(Thiessen polygon)이라고도 부른다. 각 관측소 주변의 다각형 면적($A\_i$)은 해당 관측소의 영향 면적으로 간주되며, 이를 이용해 평균 강수량($\backslash bar\{P\}$)을 계산할 수 있다: $\backslash bar\{P\}=\backslash frac\{\backslash sum\; A\_i\; P\_i\}\{\backslash sum\; A\_i\}$
* 생물학: 세포나 해면골과 같은 생물학적 구조를 모델링하는 데 사용된다. 보로노이 테셀레이션은 생물 조직의 형성을 이끄는 물리적 제약을 이해하는 기하학적 도구로 활용된다.
* 생태학: 숲이나 숲 캐노피의 성장 패턴을 연구하고, 산불 예측 모델을 개발하는 데 도움이 될 수 있다.
* 동물 행동학: 이기적 무리 이론(selfish herd theory)에서 개체 주변의 위험 영역을 모델링하는 데 사용된다.
* 계산 화학: 분자 내 핵의 위치를 기반으로 보로노이 셀을 정의하여 부분 전하를 계산하는 데 사용된다(보로노이 변형 밀도 방법). 또한, 리간드가 결합하는 부위를 보로노이 다이어그램으로 변환하여 기계 학습에 활용하기도 한다(예: 단백질 결합 포켓 분류).
* 천체물리학: 천체 이미지에서 적응형 평활 영역(adaptive smoothing regions)을 생성하여 각 영역의 신호 플럭스를 합산하는 데 사용된다. 이를 통해 이미지 전체에서 비교적 일정한 신호 대 잡음비(signal-to-noise ratio)를 유지하는 것을 목표로 한다.
* 전산 유체 역학: 점들의 보로노이 테셀레이션은 유한 체적법(finite volume method)에서 계산 영역을 정의하는 데 사용될 수 있다. 이동 메쉬 우주론 코드인 AREPO 등이 그 예이다.
* 전산 물리학: 고에너지 밀도 물리학(high-energy-density physics) 분야에서 섀도그래피(shadowgraphy)나 양성자 방사선 촬영을 통해 얻은 데이터로부터 물체의 프로파일을 계산하는 데 활용된다.

5.2. 공학

* 고분자 물리학에서는 고분자의 자유 부피를 나타내는 데 사용될 수 있다.
* 재료 과학에서는 금속 합금의 다결정 미세 구조를 표현하기 위해 보로노이 테셀레이션을 사용한다. 또한, 섬 성장 과정에서 개별 섬의 성장 속도를 추정하는 데 활용된다.
* 고체 물리학에서는 고체의 보로노이 테셀레이션인 위그너-자이츠 셀과, 결정의 역 공간(파수 공간)에서의 보로노이 테셀레이션인 브릴루앙 영역을 통해 고체 결정 구조를 분석한다.
* 기상학 및 공학 수문학에서는 특정 지역 내 강수량 자료의 가중치를 계산하는 데 사용된다. 강수량 관측소를 점으로 사용하여 다각형을 만들고, 각 관측소의 영향 면적을 기반으로 평균 강수량을 계산한다.
* 항공 분야에서는 비행 중 비상 상황 발생 시 가장 가까운 비행장을 식별하기 위해 보로노이 다이어그램을 활용한다(ETOPS 참조). 이는 해양 플로팅 차트에 중첩되어 사용된다.
* 건축 분야에서는 보로노이 패턴이 디자인 요소로 활용되기도 한다. 오스트레일리아의 골드코스트 예술 센터 재개발 공모전 당선작이 대표적인 예이다.
* 도시 계획에서는 화물 적재 구역 시스템의 효율성을 평가하는 데 보로노이 다이어그램을 사용할 수 있다.
* 광업에서는 탐사 드릴 구멍 위치를 점으로 사용하여 보로노이 다각형을 만들고, 이를 통해 귀중 물질, 광물 또는 기타 자원의 매장량을 추정한다.
* 표면 측정 분야에서는 표면 거칠기를 모델링하는 데 보로노이 테셀레이션을 사용한다.
* 로봇 공학에서는 다중 에이전트 시스템의 제어 전략이나 경로 계획 알고리즘 개발에 활용된다. 환경을 보로노이 다이어그램으로 분할하여 로봇의 이동 경로를 설정하거나, 장애물을 점으로 간주하여 이를 피하는 경로를 찾는 데 응용된다.

5.3. 정보 과학

* 컴퓨터 네트워크 분야에서는 무선 네트워크의 용량을 분석하고 유도하는 데 보로노이 다이어그램이 활용된다.
* 컴퓨터 그래픽스에서는 3차원 모델이 부서지거나 파편화되는 패턴을 계산하는 데 사용된다. 또한 절차적 생성 기법을 통해 유기적인 형태나 용암과 같은 질감(텍스처)을 만드는 데에도 응용된다.
* 자율 로봇 항법 분야에서는 로봇이 안전하게 이동할 경로를 찾는 데 보로노이 다이어그램이 이용된다. 지도상의 장애물을 점으로 간주할 경우, 보로노이 다이어그램의 가장자리는 장애물로부터 가장 멀리 떨어진 경로를 나타내므로 충돌 위험을 줄일 수 있다.
* 머신 러닝에서는 k-최근접 이웃 알고리즘(1-NN)과 같은 분류 문제를 해결하는 데 보로노이 다이어그램의 원리가 적용된다.
* 딥 러닝 기술과 결합하여, 무작위로 배치된 센서의 위치 정보, 불안정한 유체의 흐름, 지구물리학적 데이터, 3차원 난류 데이터 등을 분석하고 전체적인 장면을 재구성하는 데 보로노이 테셀레이션 기법이 쓰이기도 한다.
* 사용자 인터페이스(UI) 개발에서는 특정 지점 위로 마우스 커서가 올라갔을 때(호버 상태) 가장 적절한 상호작용 영역을 계산하는 데 보로노이 패턴이 사용될 수 있다.
* 최근접 이웃 탐색 문제, 즉 주어진 한 점에 가장 가까운 기준점을 찾는 문제는 다양한 분야에서 중요하게 다루어지며, 보로노이 영역을 활용한 데이터 구조를 통해 이 탐색 과정을 효율적으로 수행할 수 있다.
* 로봇의 동작을 계획할 때, 장애물을 피해 목적지까지 도달 가능한 경로를 찾는 방법 중 하나로 보로노이 다이어그램이 사용된다. 장애물들을 기준점으로 설정하고 생성된 보로노이 경계를 따라 이동 경로를 설정하는 방식이다. 이는 복잡한 공간을 더 단순한 차원의 골격(경로)으로 대체하는 리트랙션 접근법(retraction approach)의 예시이다.

5.4. 사회 과학

* 역학에서 보로노이 다이어그램은 전염병의 감염원 간 상관관계를 파악하는 데 사용될 수 있다. 대표적인 초기 응용 사례로 존 스노우가 1854년 브로드 스트리트 콜레라 유행을 연구한 것을 들 수 있다. 그는 런던 중심부 지도에서 특정 물 펌프를 사용한 거주 지역과 콜레라 사망자가 집중된 지역 간의 관계를 보로노이 다이어그램을 활용하여 효과적으로 보여주었다.
* 의료 진단 분야에서는 보로노이 다이어그램 기반의 근육 조직 모델을 통해 신경근 질환을 감지하는 연구가 진행되고 있다.
* 고고학의 미술사 연구에서는 조각상 머리의 대칭성을 분석하여 잘려나간 머리가 어떤 유형의 조각상에 속했는지 추정하는 데 보로노이 셀 개념을 활용한다. 사보로프 머리의 식별 과정에서 고해상도 다각형 메쉬와 함께 보로노이 셀이 사용된 것이 그 예시다.
* 방언학에서는 여러 지점에서 수집된 언어 자료를 바탕으로, 언어적 특성이 유사하게 나타나는 지역 범위를 나타내는 지도를 만들 때 보로노이 셀을 사용한다. 이를 통해 지역 간 언어적 연속성을 시각적으로 표현할 수 있다.
* 정치학에서는 여러 정당이 다양한 정책 차원에서 경쟁하는 다차원적, 다당제 경쟁 구도를 분석하는 데 보로노이 다이어그램이 활용된 바 있다.
* 보간법은 유한한 점 집합 P 상의 값만 알고 있는 함수가 있을 때, 특정 점 x에서의 함수값을 추정하는 방법 중 하나이다. 보로노이 다이어그램을 이용한 보간법은, 점 x를 포함한 전체 점들을 기준으로 x의 보로노이 영역을 설정하고, 이 영역 내에서 기존 점 P들의 보로노이 영역이 차지하는 비율에 따라 가중치를 부여하여 함수값을 계산하는 방식이다.
* 로봇의 동작 계획 수립 시, 장애물을 피해 목적지까지 안전하게 이동하는 경로를 찾는 데 보로노이 다이어그램이 사용될 수 있다. 장애물들을 점으로 간주하고 생성된 보로노이 다이어그램의 경계선을 따라 이동 경로를 설정하는 방식이다. 이러한 접근법은 복잡한 공간을 더 단순한 경로 네트워크로 표현하는 리트랙션 접근법(retraction approach)의 한 예이다.

6. 일반화 및 변형

일반적인 보로노이 셀은 집합 S 내의 단일 점에 가장 가까운 점들의 집합으로 정의되지만, n차 보로노이 다이어그램(n-th order Voronoi diagram)은 n개의 특정 점 집합 S를 n개의 가장 가까운 이웃으로 갖는 점들의 집합으로 정의되는 n차 보로노이 셀로 공간을 분할한다. 고차 보로노이 다이어그램 역시 공간을 분할한다.

고차 보로노이 다이어그램은 재귀적으로 생성될 수 있다. 집합 S에서 n^차 보로노이 다이어그램을 생성하려면 ('n' − 1)^차 다이어그램부터 시작하여 X = {x₁, x₂, ..., x_n−1}으로 생성된 각 셀을 집합 S − X에서 생성된 보로노이 다이어그램으로 대체한다.

n개의 점 집합에 대해 (n − 1)^번째 보로노이 다이어그램을 최원점 보로노이 다이어그램(farthest-point Voronoi diagram)이라고 한다. 주어진 점 집합 S = {p₁, p₂, ..., p_n}에 대해, 최원점 보로노이 다이어그램은 평면을 동일한 점 P가 가장 먼 점이 되는 셀로 나눈다. 점 P는 P의 볼록 껍질의 꼭짓점인 경우에만 최원점 보로노이 다이어그램에 셀을 갖는다. H = {h₁, h₂, ..., h_k}를 P의 볼록 껍질이라고 하자. 그러면 최원점 보로노이 다이어그램은 평면을 k개의 셀로 세분화하며, 각 셀은 H의 각 점에 해당한다. 점 q가 사이트 h_i에 해당하는 셀에 속하는 것은 d(q, h_i) > d(q, p_j)이고, 여기서 h_i ≠ p_j이며, d(p, q)는 두 점 p와 q 사이의 유클리드 거리이다. 최원점 보로노이 다이어그램의 셀 경계는 위상 트리의 구조를 가지며, 무한 반직선이 잎으로 구성된다. 모든 유한 트리는 이 방식으로 최원점 보로노이 다이어그램에서 형성된 트리와 동형이다.

정의에서 암시하듯이, 보로노이 셀은 마할라노비스 거리 또는 맨해튼 거리와 같은 유클리드 거리 외의 다른 메트릭에 대해서도 정의될 수 있다. 그러나 이러한 경우 보로노이 셀의 경계는 유클리드 경우보다 더 복잡할 수 있다.

--
[[가중 보로노이 다이어그램]](weighted Voronoi diagram)은 보로노이 셀을 정의하기 위한 점 쌍의 함수가 생성점에 할당된 곱셈 또는 덧셈 가중치에 의해 수정된 거리 함수인 다이어그램이다. 메트릭인 거리를 사용하여 정의된 보로노이 셀의 경우와 달리, 이 경우 일부 보로노이 셀이 비어 있을 수 있다. [[멱 다이어그램]](power diagram)은 점의 멱을 사용하여 원 집합에서 정의된 보로노이 다이어그램의 한 유형이다. 이는 각 원의 반지름에서 정의된 가중치가 원의 중심에서 제곱된 유클리드 거리에 추가되는 가중 보로노이 다이어그램으로 생각할 수도 있다.

$d$차원 공간에서 $n$개의 점의 보로노이 다이어그램은 $O(n^\{\backslash lceil\; d/2\; \backslash rceil\})$개의 정점을 가질 수 있으며, 이를 명시적으로 설명하는 데 필요한 메모리 양에 대해 동일한 경계가 필요하다. 따라서 보로노이 다이어그램은 중간 또는 높은 차원에서는 종종 실현 가능하지 않다. 더 공간 효율적인 대안은 근사 보로노이 다이어그램(approximate Voronoi diagram)을 사용하는 것이다.

보로노이 다이어그램은 또한 중앙 축(이미지 분할, 광학 문자 인식 및 기타 계산 응용 분야에서 활용됨), 직선 골격, 존 다이어그램과 같은 다른 기하학적 구조와 관련이 있다.

7. 알고리즘

보로노이 다이어그램을 효율적으로 계산하는 여러 알고리즘이 있다. 이 알고리즘들은 다이어그램을 직접 생성하거나, 들로네 삼각 분할을 먼저 구한 뒤 이를 이용해 간접적으로 생성하는 방식으로 나뉜다.

직접적인 방법 중 대표적인 것은 Fortune의 알고리즘으로, 평면 위의 점들로부터 보로노이 다이어그램을 O(n log n) 시간 안에 계산할 수 있다. Bowyer-Watson 알고리즘은 들로네 삼각 분할을 생성하는 알고리즘으로, O(n log n)에서 O(n²)의 시간 복잡도를 가진다. 이 알고리즘은 보로노이 다이어그램을 간접적으로 계산하는 데 활용될 수 있다. 점프 플러딩 알고리즘은 근사적인 보로노이 다이어그램을 매우 빠르게(상수 시간) 생성할 수 있어, 주로 그래픽 하드웨어에서 활용된다.

한편, 로이드의 알고리즘이나 이를 일반화한 k-평균 군집화(Linde–Buzo–Gray 알고리즘)는 보로노이 다이어그램 생성을 내부 과정(서브루틴)으로 활용한다. 이 알고리즘들은 주어진 점(씨앗점)들에 대한 보로노이 다이어그램을 만들고, 각 점을 자신이 속한 셀의 중심에 더 가까운 위치로 옮기는 과정을 반복한다. 이 과정은 반복을 통해 점들이 각 셀의 기하학적 중심에 위치하는 특별한 형태의 보로노이 다이어그램, 즉 중심 보로노이 테셀레이션으로 수렴하게 된다.

8. 3차원 보로노이 다이어그램

--

3차원 공간에서도 점의 정규 격자의 보로노이 테셀레이션은 다양한 형태를 생성한다.
* 단순 입방 격자는 입방 벌집을 생성한다.
* 육방 조밀 격자는 사다리꼴 마름모 십이면체로 공간을 테셀레이션한다.
* 면심 입방 격자는 마름모 십이면체로 공간을 테셀레이션한다.
* 체심 입방 격자는 잘린 팔면체로 공간을 테셀레이션한다.
* 서로의 중심에 정렬된 정삼각형 격자를 갖는 평행 평면은 육각형 각기둥 벌집을 생성한다.
* 특정 체심 정방 격자는 능면 육각형 십이면체로 공간을 테셀레이션한다.

3차원에서도 보로노이 메쉬를 생성할 수 있다.

--
--
--
--