---
# System prepended metadata

title: 'ADA 4.3: Closest Pair of Points 最近點對'
tags: [Closest Pair of Points, ADA 4.3]

---

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

# ADA 4.3: Closest Pair of Points 最近點對
```
經典問題： 最近點對 
```
## Define Closest Pair of Points

![](https://i.imgur.com/b5Si2YI.png)

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

輸出為最距離最接近的兩個點 aka smallest d(Pi,Pj)
```
![](https://i.imgur.com/s7Bg2Eg.png)
---

## Resolve
### 1D
![](https://i.imgur.com/R3Au9Gq.png)

```
簡化問題 降維思考
```

### 2D

- Divide-and-Conquer
![](https://i.imgur.com/NzHrlpI.png)
- Algo with Cross-Regions case
![](https://i.imgur.com/aKUgv0O.png)
```
如上面的Case 如果目前L-min = 10 R-min = 13
我們其實只要從中線往左右去找10的距離去檢查點就可以了
```

### What if 所有的點都在 δ 範圍內
![](https://i.imgur.com/rAMDWyp.png)
 ```
 已經限縮了X軸在2δ 範圍
 從Y軸來考慮 我們要找的答案如果希望<δ 那他們必定在同一個δ的範圍內 
 ```
### What if 所有的點都在 δX2δ 範圍內
![](https://i.imgur.com/IDNJuh9.png)
```
由前面的δ去定義 一個block內不可能會出現第二個點
複雜度由n/2*n/2下降到8
```
### Closet case in Cross-Regions Scope
![](https://i.imgur.com/ZC3c6m3.png)

### Algorithm Complexity
![](https://i.imgur.com/59FKtow.png)

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

### Algorithm Preprocessing
![](https://i.imgur.com/VwPt2yE.png)

### Other Algorithm
![](https://i.imgur.com/QF6J4aG.png)

---
![](https://i.imgur.com/rsIQfDk.png)
```
具備能夠將問題簡化然後解決的性質
能夠重新利用已經回傳的答案並Combined
要去檢視複雜度的重要性 -> 真的比暴力解省時間嗎
 ```
 