보로노이 다이어그램

가장 가까운 점으로 평면을 나누기

점 집합 \(P = \{p_1, \dots, p_n\}\)이 있을 때, 평면의 각 위치를 "가장 가까운 \(p_i\)"에 따라 색칠한 것이 보로노이 다이어그램이다. \(p_i\)의 셀은

$$ \text{Vor}(p_i) = \{q : \|q - p_i\| \le \|q - p_j\|,\ \forall j\}. $$

각 셀은 볼록 다각형(반평면들의 교집합)이다. \(\|q-p_i\| \le \|q-p_j\|\)는 두 점의 수직이등분선이 만드는 반평면이기 때문이다.

구조적 사실

• 보로노이 정점: 세 점에서 등거리인 점(세 셀의 만남) → 그 세 점의 외접원 중심.
• 보로노이 변: 두 점의 수직이등분선의 일부.
• 정점/변/면 수는 모두 \(O(n)\) (오일러 공식 \(V - E + F = 2\)).

델로네 삼각분할: 쌍대

보로노이의 쌍대 그래프가 델로네 삼각분할(Delaunay triangulation) 이다. 두 점의 보로노이 셀이 변을 공유하면, 델로네에서 그 두 점을 잇는다.

델로네의 정의적 성질(empty circle property):

삼각형 \(\triangle p_i p_j p_k\)가 델로네에 속할 필요충분조건은, 그 외접원 내부에 다른 점이 없는 것이다.

이는 보로노이 정점이 외접원 중심이라는 사실과 정확히 대응한다.

델로네의 최적성

델로네 삼각분할은 가능한 삼각분할 중 최소각을 최대화한다(maximize the minimum angle). "가늘고 긴 삼각형"을 피하므로 보간/메시 생성에서 선호된다. 또한:

• 유클리드 최소 신장 트리(EMST) 는 델로네의 부분 그래프다.
• 최근접 점 쌍 의 두 점은 델로네 변으로 연결되어 있다.

따라서 델로네만 \(O(n \log n)\)에 구하면 EMST, 최근접 쌍 등이 따라온다.

위로 들어 올리기(lifting)

\((x, y) \mapsto (x, y, x^2 + y^2)\)로 점을 포물면에 올리면, 델로네 삼각분할은 그 점들의 하부 볼록껍질(lower convex hull) 의 면들과 일치한다. in-circle 판정이 3D orientation(부피의 부호) 판정으로 바뀐다.

$$ \text{inCircle}(a,b,c,d) = \operatorname{sign}\det\begin{pmatrix} a_x-d_x & a_y-d_y & (a_x-d_x)^2+(a_y-d_y)^2 \\ b_x-d_x & b_y-d_y & (b_x-d_x)^2+(b_y-d_y)^2 \\ c_x-d_x & c_y-d_y & (c_x-d_x)^2+(c_y-d_y)^2 \end{pmatrix} $$

부호가 양이면 \(d\)가 \(\triangle abc\)의 외접원 내부.

알고리즘 선택

다음 강의에서 점진적 삽입(증분) 델로네를 본다.

전략: 점을 하나씩 넣고 flip

점진적 삽입 델로네는 다음을 반복한다.

1. 모든 점을 포함하는 거대한 보조 삼각형(super-triangle)으로 시작.
2. 점을 하나 삽입 → 그 점을 포함하는 삼각형을 찾고 세 조각으로 분할.
3. 새로 생긴 변들에 대해 델로네 조건(in-circle) 위반을 검사하고, 위반 시 edge flip.
4. 모든 점 삽입 후 보조 삼각형에 닿은 삼각형 제거.

무작위 순서로 삽입하면 기대 \(O(n \log n)\).

in-circle 판정

typedef long long ll;
struct P { ll x, y; };
ll cross(P o, P a, P b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
// d가 ccw 삼각형 abc의 외접원 내부면 > 0
ll inCircle(P a, P b, P c, P d) {
    ll ax=a.x-d.x, ay=a.y-d.y;
    ll bx=b.x-d.x, by=b.y-d.y;
    ll cx=c.x-d.x, cy=c.y-d.y;
    __int128 A = (__int128)(ax*ax+ay*ay)*(bx*cy-by*cx);
    __int128 B = (__int128)(bx*bx+by*by)*(ax*cy-ay*cx);
    __int128 C = (__int128)(cx*cx+cy*cy)*(ax*by-ay*bx);
    __int128 det = A - B + C;
    return det > 0 ? 1 : (det < 0 ? -1 : 0);
}

좌표가 크면 __int128로도 넘칠 수 있으니 범위를 미리 점검한다.

edge flip의 원리

볼록사각형 \(abcd\)가 대각선 \(ac\)로 두 삼각형 \(\triangle abc, \triangle acd\)로 나뉘었을 때, \(d\)가 \(\triangle abc\)의 외접원 안에 있으면 델로네 조건 위반. 대각선을 \(bd\)로 flip하면 두 삼각형이 모두 조건을 만족하게 된다.

// 변 (a,c)를 공유하는 두 삼각형에서 반대편 정점이 b, d일 때
bool needFlip(P a, P c, P b, P d) {
    // b, d가 ac의 양쪽에 있는 볼록사각형 가정
    return inCircle(a, c, b, d) > 0;
}

flip은 새 변을 만들고, 그 새 변에 인접한 삼각형들도 다시 검사해야 한다(스택/재귀로 전파).

flip의 종료성

각 flip은 "삼각분할의 lifting 높이 합"을 엄격히 줄이거나, in-circle 위반 수를 줄인다. 델로네는 모든 삼각분할 중 lifting된 lower hull에 해당하는 유일한 것이므로, flip은 유한 번 만에 멈춘다(Lawson flip의 종료성).

구현 팁

• DCEL이나 "삼각형 + 인접 삼각형 3개" 구조로 메시를 관리한다.
• 점 위치 찾기는 무작위 walk 또는 jump-and-walk로 평균 \(O(\sqrt n)\) 또는 보조 자료구조로 \(O(\log n)\).
• 동일 직선상의 점(collinear), 동일 원주상의 점(cocircular) 같은 퇴화 입력은 일관된 tie-break 규칙으로 처리.

응용 마무리

델로네를 얻으면:

• EMST: 델로네 변만 두고 크루스칼.
• 최근접 점 쌍: 델로네 변 중 최단.
• 보로노이: 각 델로네 삼각형의 외심을 잇는다.

// 델로네 변 e=(u,v)들로 EMST
sort(edges.begin(), edges.end(), byLength);   // 길이순
// union-find로 크루스칼 → EMST

연습: \(n \le 10^5\) 점의 EMST를 델로네 경유로 구하라. 무작위 셔플 후 증분 삽입이면 기대 \(O(n \log n)\)으로 충분하다.