# The Euclidean all nearest neighbor problem

歐幾里得全最近鄰問題（Euclidean All Nearest Neighbor Problem）是計算幾何中的一個經典問題。它涉及在歐幾里得空間中為一組點集中的每個點找到其最近的鄰居。具體來說，給定一組點 $P$ 在歐幾里得空間中，目標是為每個點 $p \in P$ 找到一個點 $q \in P$，使得點 $p$ 到點 $q$ 的歐幾里得距離最小（排除點 $p$ 與自身的比較）。

### 問題定義

給定：
- 一組點 $P$，包含 $n$ 個位於 $d$ 維歐幾里得空間中的點，表示為 $\mathbb{R}^d$。

目標：
- 對於每個點 $p_i \in P$，找到點 $p_j \in P$（其中 $i \neq j$），使得歐幾里得距離 $\|p_i - p_j\|$ 最小。

### 解決方法

1. **暴力法**：
- 計算每對點之間的距離。
- 時間複雜度：$O(n^2)$。
- 對於大數據集來說，這種方法效率低下。

2. **空間劃分方法**：
- **k-d 樹**：
- k-d 樹是一種在 k 維空間中組織點的空間劃分數據結構。
- 它允許有效的範圍搜索和最近鄰搜索。
- 構建 k-d 樹需要 $O(n \log n)$ 時間，最近鄰搜索平均每次查詢需要 $O(\log n)$ 時間。
- **Voronoi Diagram**：
- Voronoi Diagram 將空間劃分為基於特定點集合的距離區域。
- 它可以通過定位點所在的區域來找到最近鄰居。
- 構建 Voronoi Diagram 需要 $O(n \log n)$ 時間。
- **Delaunay 三角剖分**：
- Delaunay 三角剖分是 Voronoi Diagram的對偶圖。
- 找到最近鄰居涉及遍歷三角剖分。
- 構建 Delaunay 三角剖分也需要 $O(n \log n)$ 時間。

## Voronoi Diagram 使用在 The Euclidean all nearest neighbor problem 的證明

- 利用反證法
- 假設有一個 Voronoi Diagram ，以及建構出 Voronoi Diagram 的一些點 $j_1,..., j_n$及中心點 $i$，以及在 Voronoi Diagram 外的一個點 $k$。
- 假設線段 $L_{ik}$ 為最短邊
- 找到 $L_{ij_{n}}$ 比 $L_{ik}$ 更短 (矛盾) ，故得證。

- 時間複雜度
- $O(nlogn) + O(n) => O(n)$