# CH4 Divide and Conquer
Divide-and-Conquer Strategy 是一種常見的演算法設計策略，廣泛應用於計算機科學和數學中。
這種策略的中心思想是將一個複雜的問題分解為若干個較小且相似的子問題，然後對這些子問題分別進行解決，最後將這些子問題的解結果合併，從而得到原問題的解答。
- 分治策略通常包括以下三個步驟：
1. **分解（Divide）：** 將原問題分解為若干個規模較小且相互獨立的子問題。
2. **解決（Conquer）：** 遞迴地解決這些子問題。如果子問題規模足夠小，則直接解決。
3. **合併（Combine）：** 將子問題的解合併，得到原問題的解。
* 課本的定義:
1. A problem is divided into several subproblems of the same type, ideally of about equal size.
2. The subproblems are solved (typically recursively, though sometimes a different algorithm is employed, especially when subproblems become small enough).
3. If necessary, the solutions to the subproblems are combined to get a solution to the original problem.
### 時間複雜度
這是一個通用演算法的時間複雜度公式：
$$
T(n) =
\begin{cases}
2T\left(\frac{n}{2}\right) + S(n) + M(n), & \text{如果 } n \geq c \\
b, & \text{如果 } n < c
\end{cases}
$$
其中：
- $S(n)$：分割所需時間
- $M(n)$：合併所需時間
- $b$：常數
- $c$：常數
### Divide-and-Conquer 的應用
1. **快速排序（Quicksort）：**
- **分解：** 將數列按照基準元素劃分為兩個子數列，使得左子數列的所有元素小於基準元素，右子數列的所有元素大於基準元素。
- **解決：** 遞迴地對兩個子數列進行快速排序。
- **合併：** 由於排序是就地進行的，所以不需要特別的合併步驟。
2. **合併排序（Merge Sort）：**
- **分解：** 將數列從中間劃分為兩個子數列。
- **解決：** 遞迴地對兩個子數列進行合併排序。
- **合併：** 將兩個已排序的子數列合併成一個有序數列。
3. **二分搜尋（Binary Search）：**
- **分解：** 將已排序的數列從中間劃分為兩個子數列。
- **解決：** 根據目標值與中間元素的比較結果，在相應的子數列中遞迴地進行二分搜尋。
- **合併：** 無需特別的合併步驟，因為每次搜尋只在一個子數列中進行。
4. **找最大值 (Find The Maximun of A Set)**
- **分解：** 果數列只包含一個元素，則這個元素就是最大值。否則，將數列分成兩半，分別為左半部分和右半部分。
- **解決：** 對左半部分遞迴地找出最大值。對右半部分遞迴地找出最大值。
- **合併：** 比較左右兩半部分的最大值，取其中較大的值作為最終結果。
### 分治策略的優點
- **提高效率：** 通過將大問題轉化為小問題，減少了每次處理的數據量，有助於提高算法的效率。
- **遞迴特性：** 分治策略往往通過遞迴實現，遞迴的特性使得算法結構簡潔，邏輯清晰。
- **可並行處理：** 子問題相互獨立，適合於並行計算，可以在多處理器系統中同時處理多個子問題。
總而言之，分治策略是一種強大且高效的算法設計範式，適用於解決各類複雜問題。
### 2-D Maxima Finding Problem
2-D Maxima Finding Problem 是一種在計算幾何中常見的問題，目的是在一個二維平面上找到一組點的 maximal point。也就是說，在給定一組點 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ 中，一個點 $(x_i, y_i)$ 被稱為 maximal point，如果不存在另一個點 $(x_j, y_j)$ 使得 $x_j \geq x_i$ 且 $y_j \geq y_i$（其中至少一個不等式是嚴格的）。
另外一種講法，就是某個點的右上角沒有其他點，那就是 maximal point。
#### 範例 1
假設我們有以下幾個點：
- $(1, 2)$
- $(3, 1)$
- $(2, 4)$
- $(4, 3)$
在這個例子中，點 $(2, 4)$ 和 $(4, 3)$ 是 maximal point。因為對於這些點，沒有其他點的 x 和 y 值同時大於或等於它們的 x 和 y 值。
#### 範例 2
$(7, 13)$、$(12, 12)$、$(14, 10)$、$(15, 7)$ 都是maximal point。
#### 演算法
- **輸入：** 一組包含 n 個平面點的集合 S。
- **輸出：** 集合 S 中的 maximal points 。
- **步驟 1.**
- 如果集合 S 只包含一個點，則將該點作為 maximal points 返回。
- 否則，找到一條垂直於 x 軸的直線 L，將集合 S 分為兩個子集：$S_L$ 和 $S_R$，每個子集包含 n/2 個點。
- **步驟 2.**
- 遞迴地找到子集 $S_L$ 和 $S_R$ 的 maximal points 。
- **步驟 3.**
- 將子集 $S_L$ 和 $S_R$ 的 maximal points 投影到直線 L 上，並根據它們的 y 值對這些點進行排序。
- 進行線性掃描，丟棄 $S_L$ 中的任何 maximal points ，如果該點的 y 值小於 $S_R$ 中某個 maximal points 的 y 值。
#### 時間複雜度
$$
T(n) =
\begin{cases}
2T\left(\frac{n}{2}\right) + O(n) + O(n), & n \geq 1 \\
1, & n = 1
\end{cases}
$$
計算之後，$T(n) = O(nlog(n))$
### Closest Pair Problem
最接近點對問題（Closest Pair Problem）是計算幾何中的一個基本問題。
在平面上一組點中找到彼此最近的兩個點。
這個問題也可以推廣到更高維度。
以下是問題的定義和一些常見的解決方法：
#### 問題定義
給定平面上的一組點 $P = \{ p_1, p_2, \ldots, p_n \}$，找到距離最近的兩個點 $(p_i, p_j)$。
#### 歐幾里得距離
兩點 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之間的歐幾里得距離公式為：
$\text{distance} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$
#### 簡單方法 : 暴力法
最簡單的方法是計算每對點之間的距離，這樣的時間複雜度為 $O(n^2)$。詳細步驟為：
1. 對於每個點 $p_i$，計算其與其他每個點 $p_j$ 的距離。
2. 記錄遇到的最小距離。
#### 高效方法： Divide-and-Conquer
使用分治算法可以有效地解決最接近點對問題，類似於合併排序。這種方法的時間複雜度為 $O(n \log n)$。該算法包含以下步驟：
1. **點排序：** 根據點的 x 坐標對點集進行排序。如果兩點的 x 坐標相同，則根據 y 坐標進行排序。
2. **分解：** 將點集通過一條垂直線 $L$ 分成兩個大小相等的子集。
3. **解決：** 遞迴地在左、右兩個子集中找到最近點對。
4. **合併：** 找到跨越分割線 $L$ 的最近點對，詳細方法是：
- 僅考慮寬度為 $2\delta$ 的區域內的點，其中 $\delta$ 是遞迴步驟中找到的最小距離。
- 根據 y 坐標對這些點進行排序。
- 只需檢查區域內的常數數量的點（最多7個）來找到最近點對。
#### Divide-and-Conquer 的詳細步驟
1. **基礎情況：** 如果點的數量為 2 或 3，直接計算每對點之間的距離。
2. **遞迴情況：**
- **按 x 坐標排序。**
- **分割：** 將點集分成左右兩半。
- **遞迴調用：** 分別計算左、右子集中的最近點對。
- **合併：** 檢查分割線周圍區域的最近點對。
#### 例子
以下是一個簡化的例子：
1. **輸入：** 點 $(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)$。
2. **按 x 坐標排序：** $(2, 3), (3, 4), (5, 1), (12, 30), (12, 10), (40, 50)$。
3. **分解：** 分成左半部分 $(2, 3), (3, 4), (5, 1)$ 和右半部分 $(12, 30), (12, 10), (40, 50)$。
4. **解決：** 在左、右子集中找到最近點對。
5. **合併：** 檢查分割線周圍的最近點對。
#### 程式範例（Python）
下面是一個使用 Divide-and-Conquer 的 Python 程式碼：
```python=
import math
def euclidean_distance(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def closest_pair(points):
def closest_pair_rec(sorted_x, sorted_y):
if len(sorted_x) <= 3:
return brute_force_closest_pair(sorted_x)
mid = len(sorted_x) // 2
Qx = sorted_x[:mid]
Rx = sorted_x[mid:]
midpoint = sorted_x[mid][0]
Qy = list(filter(lambda x: x[0] <= midpoint, sorted_y))
Ry = list(filter(lambda x: x[0] > midpoint, sorted_y))
(p1, q1, min_dist1) = closest_pair_rec(Qx, Qy)
(p2, q2, min_dist2) = closest_pair_rec(Rx, Ry)
if min_dist1 <= min_dist2:
d = min_dist1
min_pair = (p1, q1)
else:
d = min_dist2
min_pair = (p2, q2)
(p3, q3, min_dist3) = closest_split_pair(sorted_x, sorted_y, d, min_pair)
if d <= min_dist3:
return min_pair[0], min_pair[1], d
else:
return p3, q3, min_dist3
def brute_force_closest_pair(points):
min_dist = float('inf')
p1, p2 = None, None
for i in range(len(points)):
for j in range(i + 1, len(points)):
dist = euclidean_distance(points[i], points[j])
if dist < min_dist:
min_dist = dist
p1, p2 = points[i], points[j]
return p1, p2, min_dist
def closest_split_pair(p_x, p_y, delta, best_pair):
mid_x = p_x[len(p_x) // 2][0]
s_y = [p for p in p_y if mid_x - delta <= p[0] <= mid_x + delta]
best = delta
len_s_y = len(s_y)
for i in range(len_s_y - 1):
for j in range(i + 1, min(i + 7, len_s_y)):
p, q = s_y[i], s_y[j]
dst = euclidean_distance(p, q)
if dst < best:
best_pair = (p, q)
best = dst
return best_pair[0], best_pair[1], best
sorted_x = sorted(points, key=lambda x: x[0])
sorted_y = sorted(points, key=lambda x: x[1])
return closest_pair_rec(sorted_x, sorted_y)
# 範例使用
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
p1, p2, min_dist = closest_pair(points)
print(f"最近的點對是 {p1} 和 {p2}，距離為 {min_dist:.4f}")
```
#### 時間複雜度
$$
T(n) =
\begin{cases}
2T\left(\frac{n}{2}\right) + O(n) + O(n), & n \geq 1 \\
1, & n = 1
\end{cases}
$$
計算之後，$T(n) = O(nlog(n))$
### Convex Hull Problem
凸包問題（Convex Hull Problem）是計算幾何中的一個基本問題，目的是在一組平面點集合中，找出能夠包圍所有點的最小凸多邊形。這個凸多邊形的邊界點組成了所謂的凸包。簡單來說，凸包是一個能包圍所有點的多邊形，使得多邊形內部的所有點都位於邊界或內部，且多邊形是凸的，即任何兩個邊上的點的連線都在多邊形內部或邊界上。
#### Graham掃描法（Graham's Scan）
Graham掃描法是解決凸包問題的一種有效方法，時間複雜度為 $O(n \log n)$，其中 $n$ 是點的數量。以下是這個算法的具體步驟：
##### 步驟一：選擇起點
1. 找到點集中最下且最左的點，這個點保證在凸包上，稱為 $P_0$。
2. 如果有多個點滿足這個條件，選擇橫坐標最小的那一個。
##### 步驟二：極角排序
1. 以 $P_0$ 為基準點，計算其他所有點相對於 $P_0$ 的極角。
2. 按照極角大小對這些點進行排序。如果兩個點的極角相同，則距離 $P_0$ 更近的點排在前面。
##### 步驟三：掃描並構建凸包
1. 將排序後的點按照順序放入一個空棧中。
2. 從棧中依次彈出點，判斷它們形成的角是否是左轉。如果不是左轉（即形成凹角或直角），則將該點彈出。
3. 重複這個過程直到處理完所有點。
#### 解釋
1. **選擇起點**：找到最下且最左的點作為起點 $P_0$。
2. **極角排序**：以起點 $P_0$ 為基準，對其他點按極角進行排序。
3. **掃描並構建凸包**：依次考察排序後的點，利用棧結構維護凸包的頂點集合，確保每次加入的點形成左轉。
#### 課本的 Divide and Conquer
1. 第一步：如果點集 S 中的點**不超過五個**，就用盡可能的搜索方法找出凸包並返回。
2. 第二步：找到一條與 x 軸**垂直的中位線**，將點集 S 分成 $S_L$ 和 $S_R$；$S_L$ 在 $S_R$ 的左側。
3. 第三步：對 $S_L$ 和 $S_R$ 遞歸地構建凸包。分別用 Hull($S_L$) 和 Hull($S_R$) 表示這些凸包。
4. 第四步：找到 $S_L$ 的一個內部點 P。找到 Hull($S_R$) 的頂點 v1 和 v2，將 Hull($S_R$) 的頂點分成兩個序列，這兩個序列相對於 P 的極角是遞增的。不失一般性，假設 v1 的 y 值大於 v2。然後按照以下步驟形成三個序列：
(a) 序列 1：Hull($S_L$) 中所有的凸包頂點，按逆時針方向排序。
(b) 序列 2：從 v2 到 v1 的 Hull($S_R$) 中的凸包頂點，按逆時針方向排序。
\(c) 序列 3：從 v2 到 v1 的 Hull($S_R$) 中的凸包頂點，按順時針方向排序。合併這三個序列，然後進行 Graham 掃描。刪除凸包中的反射點，剩下的點就是凸包的點集。
經由上面的演算法，我們就可以利用 Graham 掃描法有效地找到平面上點集的凸包。
### reference
1. [2-d maxima problem](https://www.cs.umd.edu/users/meesh/cmsc351/mount/lectures/lect2-algorithm-analysis-2dmax.pdf)
Sign in with Wallet
Connect another wallet