Closest-Pair, Quickhull & Karatsuba Multiplication

Divide-and-Conquer Applications: Closest-Pair, Quickhull, and Large Integer Multiplication

Divide-and-conquer is applied to transform quadratic algorithms into efficient sub-quadratic or near-linear solutions.

---

1. Divide-and-Conquer Closest-Pair Algorithm

In Chapter 3, the brute-force closest-pair algorithm took $\Theta(n^2)$ time. Using divide-and-conquer, the running time drops to $\Theta(n \log n)$.

Diagram loads as you scroll.

Algorithm Steps

1. Step 1: Divide: Sort points by their $x$-coordinate. Draw a vertical line $x = m$ through the median point to divide $P$ into equal subsets $P_L$ and $P_R$ of size $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$.
2. Step 2: Conquer: Recursively find the closest pair in $P_L$ with minimal distance $d_L$, and in $P_R$ with minimal distance $d_R$. Let $d = \min(d_L, d_R)$.
3. Step 3: Combine: A closer pair can only exist if one point is in $P_L$ and the other in $P_R$. Such points must lie within a vertical strip of width $2d$ centered at $x = m$ ($m - d \le x \le m + d$).
   • Filter all points falling inside the strip and sort them by $y$-coordinate.
   • For each point $p$ in the strip, only points with $y$-coordinates in $[y_p, y_p + d]$ need to be checked.
   • Geometric Fact: At most 6 points can fit into a $d \times 2d$ rectangle on the other side of the dividing line without violating the property that all points on each side are at least $d$ apart!
   • Hence, each point in the strip is compared against at most 5 to 7 neighboring points.

Complexity Analysis

By pre-sorting the points by $x$ and maintaining a list sorted by $y$:

$$T(n) = 2 T(n / 2) + \Theta(n)$$

By the Master Theorem ($a = 2, b = 2, d = 1 \implies a = b^d$):

$$T(n) \in \Theta(n \log n)$$

---

2. Quickhull (Convex Hull by Divide-and-Conquer)

Inspired by Quick Sort, Quickhull constructs the convex hull of $n$ points in average time $\Theta(n \log n)$:

1. Identify extreme points with minimum $x$ ($p_1$) and maximum $x$ ($p_n$). The line segment $\overline{p_1 p_n}$ divides the remaining points into two subsets:
   • Upper set $S_1$: Points lying above $\overline{p_1 p_n}$.
   • Lower set $S_2$: Points lying below $\overline{p_1 p_n}$.
2. In $S_1$, locate point $p_{\max}$ with the maximum perpendicular distance to $\overline{p_1 p_n}$. Point $p_{\max}$ is guaranteed to be an extreme point of the convex hull!
3. Points inside the triangle $\triangle p_1 p_{\max} p_n$ cannot be extreme points and are discarded.
4. Recursively repeat for points outside the segments $\overline{p_1 p_{\max}}$ and $\overline{p_{\max} p_n}$.

• Average Case: $\Theta(n \log n)$.
• Worst Case: $\Theta(n^2)$ (when points lie on a circle and almost no points are discarded).

---

3. Multiplication of Large Integers (Karatsuba Algorithm)

Multiplying two $n$-digit integers using pen-and-paper school multiplication takes $\Theta(n^2)$ single-digit multiplications.

Let $A$ and $B$ be two $n$-digit integers. Dividing each into two $m$-digit halves ($m = \lfloor n/2 \rfloor$):

$$A = a_1 \cdot 10^m + a_0$$ $$B = b_1 \cdot 10^m + b_0$$

Direct multiplication yields:

$$A \times B = (a_1 \cdot 10^m + a_0)(b_1 \cdot 10^m + b_0) = (a_1 b_1) 10^{2m} + (a_1 b_0 + a_0 b_1) 10^m + (a_0 b_0)$$

This requires 4 multiplications ($a_1 b_1$, $a_1 b_0$, $a_0 b_1$, $a_0 b_0$), giving recurrence $T(n) = 4T(n/2) + \Theta(n) \implies \Theta(n^2)$, which is no faster than brute force!

Karatsuba’s Insight: Reduce to 3 Multiplications

Compute:

1. $c_2 = a_1 \times b_1$
2. $c_0 = a_0 \times b_0$
3. $c_1 = (a_1 + a_0) \times (b_1 + b_0) - c_2 - c_0$

Observe that:

$$(a_1 + a_0)(b_1 + b_0) - a_1 b_1 - a_0 b_0 = a_1 b_0 + a_0 b_1$$

Thus, $A \times B$ is computed with only 3 multiplications instead of 4:

$$A \times B = c_2 \cdot 10^{2m} + c_1 \cdot 10^m + c_0$$

---

Midterm Case Study: Compute $2134 \times 5687$

Using the divide-and-conquer formula for $2134 \times 5687$:

• Number of digits $n = 4 \implies m = 2$.
• $A = 2134 \implies a_1 = 21, \ a_0 = 34$.
• $B = 5687 \implies b_1 = 56, \ b_0 = 87$.

Step 1: Compute $c_2$

$$c_2 = a_1 \times b_1 = 21 \times 56 = 1176$$

Step 2: Compute $c_0$

$$c_0 = a_0 \times b_0 = 34 \times 87 = 2958$$

Step 3: Compute $c_1$

$$\begin{aligned} (a_1 + a_0) &= 21 + 34 = 55 \\ (b_1 + b_0) &= 56 + 87 = 143 \\ (a_1 + a_0)(b_1 + b_0) &= 55 \times 143 = 7865 \\ c_1 &= 7865 - c_2 - c_0 = 7865 - 1176 - 2958 = 3731 \end{aligned}$$

Step 4: Combine the Products

$$\begin{aligned} A \times B &= c_2 \cdot 10^4 + c_1 \cdot 10^2 + c_0 \\ &= 1176 \times 10^4 + 3731 \times 10^2 + 2958 \\ &= 11{,}760{,}000 + 373{,}100 + 2{,}958 \\ &= \mathbf{12{,}136{,}058} \end{aligned}$$

Complexity Analysis

The recurrence for Karatsuba’s algorithm is:

$$T(n) = 3 T(n / 2) + \Theta(n)$$

Here $a = 3, b = 2, d = 1$. Since $a = 3 > b^d = 2^1 = 2$, Master Theorem Case 3 gives:

$$T(n) \in \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$$

This represents a substantial asymptotic speedup over standard $\Theta(n^2)$ multiplication.

---

Exercises

Exercise 1

In the divide-and-conquer closest-pair algorithm, why are at most 6 points inspected in the opposite half of the strip for each point?

Show solution ↓Hide solution ↑

Solution

Let the vertical strip have width $2d$, extending distance $d$ to the left and $d$ to the right of the dividing line.

• All points in the left half are at pairwise distance at least $d$ from each other.
• All points in the right half are at pairwise distance at least $d$ from each other.

Consider a rectangle of width $d$ and height $d$ in the right half. The maximum number of points that can be placed in this $d \times d$ square such that no two are closer than $d$ is at most 4 (the four corners). Extending over the candidate band of height $d$ across both halves, at most 6 points can fit within distance $d$ of any candidate point.

Exercise 2

Compute the product $12 \times 34$ using Karatsuba’s 3-multiplication method ($m = 1$).

Show solution ↓Hide solution ↑

Solution

$A = 12 \implies a_1 = 1, a_0 = 2$. $B = 34 \implies b_1 = 3, b_0 = 4$. $m = 1$.

1. $c_2 = a_1 b_1 = 1 \times 3 = 3$.
2. $c_0 = a_0 b_0 = 2 \times 4 = 8$.
3. $c_1 = (1 + 2)(3 + 4) - 3 - 8 = 3 \times 7 - 11 = 21 - 11 = 10$.

Combine:

$$A \times B = c_2 \cdot 10^2 + c_1 \cdot 10^1 + c_0 = 3(100) + 10(10) + 8 = 300 + 100 + 8 = 408$$

Verification: $12 \times 34 = 408$.