# Voronoi와 Delaunay

Voronoi Diagram과 Delaunay Triangulation은 평면의 점 집합에서 "가장 가까운 점" 구조를 다루는 쌍대 개념입니다. 구현 난도는 높지만, 문제에서 어떤 성질을 써야 하는지 알면 closest pair, nearest neighbor, Euclidean MST를 더 구조적으로 볼 수 있습니다.

## 문제 신호

| 문제 표현 | 관점 |
| --- | --- |
| 각 위치에서 가장 가까운 site | Voronoi diagram |
| nearest neighbor graph의 후보를 줄이기 | Delaunay triangulation |
| Euclidean MST 후보 edge | Delaunay edge 포함 |
| 세 점의 외접원 안에 다른 점이 없는가 | Delaunay predicate |
| 평면 subdivision과 nearest region | Voronoi cell |

대부분의 대회에서는 Voronoi/Delaunay를 직접 구현하기보다, 성질을 이용해 후보를 줄이거나 특수 조건에서 우회합니다.

## 쌍대 관계

Voronoi Diagram은 점마다 가장 가까운 영역을 나눕니다. Delaunay Triangulation은 Voronoi cell이 변을 공유하는 점들을 간선으로 연결합니다.

```text
Voronoi vertex  <->  Delaunay triangle (일반 위치)
Voronoi edge    <->  Delaunay edge
Voronoi cell    <->  input point
```

이 관계 때문에 nearest 구조 문제는 Delaunay graph 위의 sparse graph 문제로 바뀔 수 있습니다.

## Empty Circumcircle

세 점 `a, b, c`가 Delaunay triangle이 되려면, 그 외접원 내부에 다른 점이 없어야 합니다.

```text
no point p lies strictly inside circumcircle(a, b, c)
```

이 조건은 determinant로 판정할 수 있습니다. 아래 코드는 `a,b,c`의 방향을 보정하여, 비공선 삼각형의 외접원 내부이면 양수를 반환합니다.

incircle 부호 보정 함수는 triangle 방향을 내부에서 반영합니다. 세 기준점이 일직선이면 외접원이 정의되지 않으므로 호출하지 않습니다. 고정 EPS는 모든 좌표 크기에 대한 정확성 보장이 아닙니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <cmath>
using namespace std;

struct Point2D {
    long double x;
    long double y;
};

long double orient(const Point2D& a, const Point2D& b, const Point2D& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

long double inCircleValue(Point2D a, Point2D b, Point2D c, Point2D p) {
    long double ax = a.x - p.x;
    long double ay = a.y - p.y;
    long double bx = b.x - p.x;
    long double by = b.y - p.y;
    long double cx = c.x - p.x;
    long double cy = c.y - p.y;

    long double det =
        (ax * ax + ay * ay) * (bx * cy - by * cx)
      - (bx * bx + by * by) * (ax * cy - ay * cx)
      + (cx * cx + cy * cy) * (ax * by - ay * bx);

    if (orient(a, b, c) < 0) {
        det = -det;
    }
    return det;
}

bool strictlyInsideCircumcircle(Point2D a, Point2D b, Point2D c, Point2D p) {
    const long double EPS = 1e-18L;
    return inCircleValue(a, b, c, p) > EPS;
}
```

정수 좌표가 작으면 `__int128` determinant로 exact predicate를 만들 수 있습니다. 실수 좌표에서는 EPS와 degeneracy가 어렵습니다.

## Delaunay와 Euclidean MST

Euclidean MST의 모든 간선은 Delaunay triangulation의 간선에 포함됩니다.

```text
EMST edges ⊆ Delaunay edges
```

따라서 Delaunay graph를 만들 수 있으면, 그 위에서 Kruskal을 돌려 Euclidean MST를 구할 수 있습니다. 다만 Delaunay triangulation 구현 자체가 쉽지 않으므로, 제약이 작으면 모든 간선 또는 grid/sweep 최적화를 먼저 검토합니다.

## Voronoi Cell의 반평면

한 site `p`의 Voronoi cell은 다른 모든 site `q`에 대해 `p`가 `q`보다 가까운 반평면의 교집합입니다.

```text
dist(x, p) <= dist(x, q)
```

전개하면 두 점의 수직이등분선이 만들고, `p` 쪽 반평면을 취합니다. 그래서 Voronoi cell 하나는 half-plane intersection으로도 구할 수 있습니다.

## 구현 전략

| 목표 | 현실적인 접근 |
| --- | --- |
| 점 수 작음 | 모든 pair/triangle 검사 |
| closest pair만 필요 | sweep 또는 divide-and-conquer |
| EMST | 가능한 후보 edge 축소 후 Kruskal |
| 전체 Delaunay 필요 | 검증된 library 또는 randomized incremental |
| 한 cell만 필요 | half-plane intersection |

Voronoi/Delaunay 전체 구현은 degenerate case가 많습니다. 온라인 저지에서는 입력이 일반 위치인지, 같은 원 위 네 점이 가능한지 반드시 봅니다.

## Degeneracy

| 상황 | 문제 |
| --- | --- |
| 같은 점 중복 | nearest region이 불명확 |
| 세 점 collinear | 외접원이 없음 |
| 네 점 cocircular | Delaunay triangulation이 유일하지 않음 |
| 매우 가까운 실수 좌표 | predicate 오차 |
| bounding box 없는 Voronoi | 무한 cell 존재 |

문제에서 "no three collinear", "no four cocircular" 같은 조건이 있으면 구현이 크게 단순해집니다.

## 시간 복잡도

| 작업 | 대표 시간 |
| --- | ---: |
| 모든 pair 거리 | `O(N^2)` |
| closest pair sweep | `O(N log N)` |
| Delaunay triangulation | `O(N log N)` expected/typical |
| Voronoi cell 하나 via HPI | `O(N log N)` |
| 모든 triangle empty circle brute force | `O(N^4)` |

직접 Delaunay를 구현하는 대신 문제의 제약에 맞는 더 단순한 구조가 있는지 먼저 찾습니다.