# Power Diagram

Power Diagram은 점마다 가중치가 있을 때 "가까움"을 `거리 제곱 - weight`로 정의하는 weighted Voronoi 구조입니다. 일반 Voronoi가 가장 가까운 점을 나누는 구조라면, Power Diagram은 반지름이 다른 원이나 영향력이 다른 점의 지배 영역을 선형 경계로 나눕니다.

## 문제 신호

| 문제 표현 | Power Diagram 관점 |
| --- | --- |
| 점마다 반지름이나 영향력이 다르다 | additive weight |
| `dist^2 - r^2`가 최소인 영역 | power distance |
| weighted Voronoi가 필요하다 | power cell |
| 원들의 radical axis가 나온다 | 두 weighted site의 경계 |
| 일반 Voronoi보다 큰 점이 영역을 더 가져간다 | weight가 cell을 밀어냄 |

Power distance는 아래처럼 정의합니다.

```text
power_i(x) = |x - p_i|^2 - w_i
```

가중치가 클수록 같은 위치에서 power value가 작아지므로 더 넓은 영역을 차지할 수 있습니다.

## 경계가 직선이 되는 이유

두 site `a`, `b`의 경계는 `power_a(x) = power_b(x)`입니다.

```text
|x - a|^2 - w_a = |x - b|^2 - w_b
```

제곱항 `|x|^2`가 양쪽에서 사라지므로 남는 식은 일차식입니다.

```text
2(b - a) dot x = |b|^2 - |a|^2 + w_a - w_b
```

따라서 Power Diagram의 cell은 여러 half-plane의 교집합입니다. 일반 Voronoi와 마찬가지로 볼록한 영역이며, 무한하거나 퇴화할 수도 있습니다. 다만 어떤 site는 weight 차이 때문에 cell이 아예 사라질 수 있습니다.

## 작은 예시

두 점이 있습니다.

```text
A = (0, 0), w_A = 0
B = (4, 0), w_B = 12
```

경계는 아래 식입니다.

```text
x^2 + y^2 = (x - 4)^2 + y^2 - 12
0 = -8x + 16 - 12
x = 0.5
```

가중치가 없었다면 경계는 `x = 2`입니다. `B`의 weight가 크기 때문에 `B`가 왼쪽까지 더 넓게 가져가고, 경계가 `A` 쪽으로 밀립니다.

## Cell 계산

특정 site `i`의 cell을 계산하려면 모든 다른 site `j`에 대해 아래 조건을 만족해야 합니다.

```text
power_i(x) <= power_j(x)
```

이를 half-plane으로 바꿔서 bounding box와 함께 교집합을 구합니다.

```text
2(p_j - p_i) dot x <= |p_j|^2 - |p_i|^2 + w_i - w_j
```

site 수가 작으면 site마다 half-plane intersection을 돌려도 됩니다. 전체 diagram을 효율적으로 만들려면 regular triangulation이나 lifting 관점을 사용하지만, 구현 난도는 훨씬 높습니다.

Power diagram은 제곱 거리에서 가중치를 빼는 모델입니다. 거리에서 가중치를 빼거나 거리에 가중치를 곱하는 다른 weighted Voronoi와 구분합니다. cell은 비어 있거나 무한할 수 있습니다. 동일 좌표면 더 큰 weight가 지배하며 같은 weight의 tie 정책은 별도로 정합니다.

## Radical Axis와 원

원 `i`의 중심을 `p_i`, 반지름을 `r_i`라고 하면 `w_i = r_i^2`로 둘 수 있습니다. 그러면 power distance는 점이 원에 대해 가지는 power와 같습니다.

두 원에 대한 power가 같은 점들의 집합은 radical axis입니다. 그래서 Power Diagram은 여러 원의 radical axis들이 만드는 cell 구조로 볼 수 있습니다.

## 시간 복잡도

| 접근 | 시간 |
| --- | ---: |
| 한 site cell을 모든 half-plane으로 계산 | `O(N log N)` 또는 구현에 따라 `O(N^2)` |
| 모든 site에 대해 반복 | `O(N^2 log N)` 이상 |
| regular triangulation 기반 전체 구성 | 구현/라이브러리 의존 |

대회에서는 보통 전체 diagram 라이브러리 구현보다 "특정 점이 어느 site에 속하는지", "site 몇 개의 경계가 어디인지", "cell이 비었는지" 같은 제한된 형태로 나옵니다.

## 로컬 연습: Power Cell 경계와 빈 Cell


[Power Diagram](https://h.readiz.com/learn/geometry-robustness-and-duality/power-diagram)의 power 부등식을 사용합니다. A=(0,0,w=0), B=(4,0,w=12)의 경계는 x=0.5입니다. 여기에 C=(-4,0,w=20)를 추가하면 A가 C보다 가까운 영역은 x>=0.5가 되어 A의 cell은 선으로 퇴화합니다. C의 w를 24로 바꾸면 x>=1과 x<=0.5를 동시에 만족해야 하므로 A의 cell은 비어 있습니다.