기지국 커버리지와 배달 권역
각 단말이 가장 가까운 기지국에 접속하면 서비스 권역은 보로노이 셀이 된다. 배달 지점의 담당 구역 분할, 상권 분석에도 같은 수학이 쓰인다.
최근접 사이트 기준으로 평면을 분할하는 보로노이 다이어그램 시각화.
사이트를 흩뿌려 평면을 가장 가까운 점 기준의 볼록 셀로 분할합니다. 사이트를 옮기며 셀 경계가 재구성되는 과정과 들로네 삼각분할의 쌍대 관계를 확인합니다.
사이트를 흩뿌리면 평면의 모든 위치가 가장 가까운 사이트로 칠해져 볼록한 셀로 분할된다. 경계는 두 사이트로부터 등거리인 점들이다. 인접한 셀의 사이트를 이으면 Delaunay 삼각분할 — 메시 생성·최근접 탐색·자연스러운 지도를 떠받치는 기하학적 듀얼 — 이 드러난다.
시간복잡도 O(n log n) (Fortune)
V(p_i) = { x : dist(x, p_i) <= dist(x, p_j) for all j }
각 단말이 가장 가까운 기지국에 접속하면 서비스 권역은 보로노이 셀이 된다. 배달 지점의 담당 구역 분할, 상권 분석에도 같은 수학이 쓰인다.
최근접 지점을 매번 전수 비교하면 O(n)이다. 보로노이의 듀얼인 들로네 삼각분할을 미리 만들어 두면 이웃 탐색이 크게 빨라진다. 게임의 세력권 계산과 절차적 맵 생성에도 쓰인다.
유클리드 거리에서 셀 경계는 두 사이트의 수직이등분선이다. 맨해튼 거리로 바꾸면 경계가 꺾인 선이 된다. 거리의 정의가 기하 구조를 결정한다.