# Voronoi Diagrams - Post Office Problem
計算幾何 Min-Te Sun, Ph.D

## Service Area of Each Post Office
### Assumptions
1. 每個 site (提供服務的點)，提供服務的cost都相同
2. cost of transportation 與距離成正比
3. 假設空間中無障礙物

### Voronoi Assignment Model
1. Voronoi assignment model
-> every point is assigned to the nearest site(提供服務的點)
2. Voronoi diagram
-> 將一個空間依據Voronoi assignment model切割成多個subdivision

### Definition of Voronoi Diagram
* P 集合是將平面細分為 n 個 cell，
=> P = {$p_1$ , $p_2$ ,..., $p_n$ } 是 n 個不同site
* q 為一個點，且在P集合中與 $p_i$ 距離最短
=> dist(q, $p_i$) < dist(q, $p_j$) for each $p_j$ ∈ P with j ≠ i
* 假設cell 中包含site X，而相對於其他site，與site X有最短距離的點集合，即為cell的點集合

### The Case of Two Sites and Its Generalization
* 當點在$p_1$和$p_2$的垂直平分線上，此時該點到$p_1$和$p_2$的距離相同，因此得到以下結論：
* 當一個點在A區域時，其距離會較$p_1$近
* 當一個點在B區域時，其距離會較$p_2$近
* 所以有n個site時，可透過將每個site用垂直平分線分成兩個集合後，並找出他們的交集，即可得到第i個cell的集合 V($p_i$)
=> 

### Computing Voronoi Diagram
Fortune’s algorithm
– Ω(nlogn)
– This algorithm is optimal since sorting n real
numbers is reducible to the problem of
computing Voronoi diagram
– A “variation” of plane sweep