**보로노이 다이어그램(Voronoi Diagram)**은 평면상의 점들을 기준으로 공간을 분할하는 특별한 테셀레이션 패턴입니다. 각 영역(셀)은 해당 영역 내 모든 점이 다른 어떤 점보다 특정 기준점에 더 가깝다는 특성을 가집니다.
델로네 삼각분할(Delaunay & Urquhart )과의 관계
보로노이 다이어그램은 델로네 삼각분할의 듀얼 그래프(dual graph)입니다. 보로노이 꼭짓점은 **델로네 면(삼각형)**이 되고, 델로네 꼭짓점은 보로노이 영역이 됩니다.
알고리즘
델로네 삼각분할 수행
듀얼 그래프 구성
아이디어
보로노이 다이어그램은 엔지니어링에서는 꽤나 유명합니다. K-means 알고리즘과 더불어서, 보로노이는 클러스터링을 구성하는 방법으로 수행할 수 있으며, 토폴로지 혹은 메시를 구성하는 주요 알고리즘이기도 합니다.
멀티플레이어 공간 분할
