# Geometry Robustness and Duality

Geometry Robustness and Duality는 robust predicate, Voronoi/Delaunay, Power Diagram, 3D lifting, Regular Triangulation을 하나의 계산기하 심화 흐름으로 묶는 허브입니다. 이 묶음은 전체 구현을 외우기보다 "어떤 predicate가 필요하고, 어떤 duality로 문제를 낮출 수 있는가"를 먼저 판단해야 합니다.


## 모델 선택 표

| 문제 신호 | 먼저 볼 페이지 |
| --- | --- |
| orientation, incircle, EPS 정책이 답을 좌우한다 | [Robust Geometry Predicates](pages/robust-geometry-predicates.md) |
| weighted site의 nearest cell이 필요하다 | [Power Diagram](pages/power-diagram.md) |
| Delaunay edge flip과 incircle degeneracy가 핵심이다 | [Robust Delaunay](pages/robust-delaunay.md) |
| 2D weighted 구조를 3D lower hull로 이해해야 한다 | [Regular Triangulation](pages/regular-triangulation.md) |
| signed volume, visible face, horizon edge가 필요하다 | [3D Convex Hull](pages/3d-convex-hull.md) |

가장 먼저 볼 것은 "좌표를 실제로 만들 것인가, 부호만 판정할 것인가"입니다. predicate만 필요하면 exact arithmetic으로 안정성을 잡고, cell이나 교점 좌표가 필요하면 construction 오차와 tie policy를 따로 설계합니다.

## Robustness와 Duality를 분리하기

| 질문 | Robustness 관점 | Duality 관점 |
| --- | --- | --- |
| 세 점의 방향이 필요한가 | orientation 부호와 overflow | convex hull, sweep ordering |
| 점이 원 안에 있는가 | incircle determinant | Delaunay edge legality |
| weighted nearest가 필요한가 | power distance 비교 | Power Diagram과 regular triangulation |
| 2D 경계가 복잡한가 | half-plane intersection 안정성 | lifting 후 lower envelope |
| 입력이 degeneracy를 포함하는가 | tie-breaking policy | 여러 가능한 triangulation |

robust predicate 없이 duality만 쓰면 구현이 불안정해지고, duality 없이 predicate만 외우면 왜 그 부호를 보는지 흐름이 끊깁니다.

## 쓰지 말아야 할 경우

- 좌표 범위가 큰 정수인데 모든 predicate를 `double` cross product로 처리합니다.
- weighted Voronoi 문제인데 weight가 반지름인지 반지름 제곱인지 확인하지 않습니다.
- 한 cell만 필요할 뿐인데 full Delaunay 또는 regular triangulation을 구현하려고 합니다.
- 3D hull degeneracy를 처리할 준비가 없는데 regular triangulation 전체 구조를 직접 만듭니다.
- EPS comparator로 balanced tree의 strict ordering을 깨뜨립니다.

## 연습

[정수 선분 교차 실습](pages/robust-geometry-predicates.md)과 [Power Cell 경계 실습](pages/power-diagram.md)을 각 설명 뒤에서 검증합니다.