보로노이 다이어그램(Voronoi Diagram)은 $2$차원 좌표평면에 점들이 존재할 때 평면을 그 위치에서 가장 가까운 점에 따라 분할한 것을 의미한다. 다음 그림은 점 $20$개가 있는 보로노이 다이어그램의 예시이다.
보로노이 다이어그램은 거리가 가까운 점들의 수직이등분선을 적절하게 이으면 그릴 수 있다.
들로네 삼각분할(Delaunay Triangulation)은 $2$차원 좌표평면에 점들이 존재할 때 점들을 이어서 여러 개의 삼각형을 만드는데 삼각형의 외접원이 삼각형의 세 꼭짓점 외의 다른 점을 포함하는 경우가 생기지 않게 하는 분할 방법이다. 다음 그림은 점 $10$개가 있는 들로네 삼각분할의 예시이다.
보로노이 다이어그램과 들로네 삼각분할은 쌍대 관계(Duality)에 있으며 둘 중 하나를 알면 다른 하나를 구할 수 있다. 점들에 대한 보로노이 다이어그램을 구했을 경우 다이어그램에서 인접한 영역에 존재하는 점들을 서로 연결하면 들로네 삼각분할이 되고, 들로네 삼각분할을 구했을 경우 각각의 삼각형의 외심을 찾은 다음 인접한 삼각형의 외심을 모두 연결하면 보로노이 다이어그램이 된다.
※ 추후 내용 추가 예정
[연습문제]
BOJ 19552. 데이터 제작 (Diamond III)
출제자의 의도가 들로네 삼각분할을 이용하는 것이라고 한다. 최소한의 점들로 영역을 구성하고 나머지 점들은 영역이 늘어나지 않도록 배치하고 이어주면 된다.
BOJ 7890. 가까운 점 찾기 (Diamond I)
점들에 대한 들로네 삼각분할을 구했을 때 서로 이어진 점들의 거리만 비교하면 된다.
'Algorithm > G. Geometry' 카테고리의 다른 글
| 100. Rotating Calipers (0) | 2021.09.02 |
|---|---|
| 99. Andrew's Algorithm (2) | 2021.08.31 |
| 98. Graham Scan (0) | 2021.08.31 |
| 97. Convex Hull (0) | 2021.08.31 |
| 96. Line Intersection (4) | 2021.08.30 |
