보로노이 다이어그램

보로노이 다이어그램은 생성점이라 부르는 점들에 평면을 나누어 줍니다. 각 생성점은 자신까지의 거리가 다른 어떤 생성점까지의 거리보다 크지 않은 점들의 영역을 가집니다. 그림은 평면을 들여다보는 창이며, 영역 안의 명암은 시각적 표현일 뿐입니다. 파란 탐침은 가장 가까운 생성점까지 닿는 빈 원의 중심입니다. 여기서는 생성점을 옮겨 이웃 영역의 변화를 보고, 각 생성점에서 영역을 자라게 하며, 들로네 삼각분할을 보고, 생성점들을 고르게 퍼뜨려 벌집 모양에 가까워지게 할 수 있습니다.

생성점 $p$까지의 거리가 다른 생성점 $q$까지의 거리보다 크지 않은 점들은 $pq$의 수직이등분선을 경계로 하는 반평면을 이룹니다. $p$의 영역은 다른 생성점마다 하나씩 있는 이 반평면들의 교집합이므로 볼록합니다. 이등분선 중 일부만 변이 됩니다. $p$의 영역과 변을 공유하는 영역의 생성점이 이웃 생성점이며, 나머지 반평면들은 이미 영역 전체를 포함합니다. 테두리는 창을 제한할 뿐입니다. 영역이 무한히 뻗는 것은 그 생성점이 모든 생성점의 볼록 껍질 경계에 있을 때, 그리고 그때뿐입니다.

세 개 이상의 영역이 만나는 꼭짓점은 각 생성점에서 같은 거리에 있으므로, 그 생성점들을 지나는 원의 중심입니다. 원 내부에는 생성점이 없습니다. 만약 있다면 그 생성점이 꼭짓점에 더 가까워서, 꼭짓점은 그 생성점의 영역에 속해야 합니다. 보통 꼭짓점에서는 정확히 세 영역이 만납니다. 정사각 격자처럼 정확히 네 생성점이 하나의 빈 원 위에 놓이면 네 영역이 만납니다. 무작위로 흩어진 생성점에서는 이런 일이 거의 일어나지 않습니다.

성장은 모든 생성점에서 같은 속도로 원판을 키웁니다. 각 지점에는 가장 가까운 생성점에서 먼저 도달하므로, 성장 전선은 정확히 변을 따라 만납니다. 작은 화면은 같은 성장을 옆에서 보여 줍니다. 각 지점의 높이는 가장 가까운 생성점까지의 거리로, 생성점 위에 선 원뿔 $z = |x - s|$ 중 가장 낮은 높이입니다. 능선은 변에 해당하고 성장은 물이 차오르는 것에 해당합니다. 마지막으로 잠기는 곳은 테두리 안 지형의 가장 높은 지점이며, 중심을 테두리 안에 둔 가장 큰 빈 원의 중심입니다.

삼각분할은 영역들이 변을 공유할 때 두 생성점을 잇고, 정사각 격자처럼 네 개 이상의 생성점이 하나의 빈 원 위에 있으면 점선 대각선을 더합니다. 모든 생성점이 한 직선 위에 있는 경우를 제외하면 결과는 들로네 삼각분할입니다. 각 삼각형의 외접원은 다이어그램의 꼭짓점을 중심으로 하는 빈 원입니다.

고르게 하기는 각 생성점을 테두리로 잘라 낸 자기 영역의 무게중심으로 옮기고 영역을 다시 만드는 과정을 반복합니다. 이것이 로이드 알고리즘입니다. 작은 그래프는 테두리 안의 한 점에서 가장 가까운 생성점까지의 거리 제곱의 평균을, 생성점 하나당 테두리 면적으로 나눈 값을 그립니다. 어떤 회차도 이 값을 높일 수 없습니다. 생성점이 고정되어 있으면 가장 가까운 생성점에 배정한 영역이 값을 최소화하고, 영역이 고정되어 있으면 무게중심이 최소화합니다. 벌집 선은 하한으로, 같은 크기의 정육각형들 중심에 생성점을 둔 경우의 값입니다. 흩어진 생성점에서 시작하면 완벽한 벌집이 아니라 가까운 안정 상태에서 멈춥니다. 보통 오각형과 칠각형이 나란히 남아 결정의 전위와 비슷한 모습을 보입니다.

다이어그램은 1908년에 임의 차원에서 이러한 분할을 연구한 게오르기 보로노이의 이름을 땄으며, 삼각분할은 1934년에 이를 기술한 보리스 들로네의 이름을 땄습니다.