###### tags: `ADA 4.3` `Closest Pair of Points`

# ADA 4.3: Closest Pair of Points 最近點對

經典問題： 最近點對 

## Define Closest Pair of Points


兩個以上的點 座標範圍皆定義於第一象限(+,+)

輸出為最距離最接近的兩個點 aka smallest d(Pi,Pj)

---

## Resolve
### 1D

簡化問題 降維思考

### 2D

- Divide-and-Conquer
- Algo with Cross-Regions case

如上面的Case 如果目前L-min = 10 R-min = 13
我們其實只要從中線往左右去找10的距離去檢查點就可以了

### What if 所有的點都在 δ 範圍內

 已經限縮了X軸在2δ 範圍
 從Y軸來考慮 我們要找的答案如果希望<δ 那他們必定在同一個δ的範圍內 

### What if 所有的點都在 δX2δ 範圍內

由前面的δ去定義 一個block內不可能會出現第二個點
複雜度由n/2*n/2下降到8

### Closet case in Cross-Regions Scope

### Algorithm Complexity

 定義BaseCase
 先sort X 才能切開
 找出左右兩側最靠近的Pair
 
 開始解析Cross-Regions Case
 將不在範圍內的點去除
 依照Ｙ軸排序
 計算每一個點對於自身距離與其他8個block的距離

### Algorithm Preprocessing

### Other Algorithm

---

具備能夠將問題簡化然後解決的性質
能夠重新利用已經回傳的答案並Combined
要去檢視複雜度的重要性 -> 真的比暴力解省時間嗎