Chapter 3: Convex Hull

Source files used: Convex_hull (Lecture 2 notes, pages 1 to 7A and Example A), MIT6_046JS15_pset1 (Problem 1-2 as practice); textbook Section 33.3 (sec33.3) as support. No worked examples are included.

1. Big Picture

Convex hull is the lecture’s first full divide-and-conquer algorithm.

The Master Theorem guide asked: how do you solve $T(n)=aT(n/b)+f(n)$? This guide asks: how do you design the merge step so that $f(n)=\Theta(n)$ instead of $\Theta(n^2)$?

$$\boxed{\text{Split by }x\text{, recurse, merge with two tangents in }\Theta(n)\Rightarrow\Theta(n\lg n).}$$

New ideas:

• brute force is $O(n^3)$,
• the merge step is “find the upper and lower tangents, then cut and paste”,
• the two-finger tangent search makes the merge linear,
• the textbook adds Graham’s scan and Jarvis’s march as alternatives.

---

2. Core Ideas

2.1 Problem Statement

Given $n$ points in the plane:

$$S=\{(x_i,y_i)\mid i=1,2,\dots,n\}$$

For convenience the lectures assume no two points share an $x$ coordinate, no two share a $y$ coordinate, and no three are on a line.

Convex hull $CH(S)$: the smallest polygon containing all points in $S$.

Picture: the points are nails, and $CH(S)$ is the shape of a rubber band stretched around all of them.

---

2.2 Representation

The lectures represent $CH(S)$ as the sequence of boundary points in clockwise order, stored as a doubly linked list:

$$p\leftrightarrow q\leftrightarrow r\leftrightarrow s\leftrightarrow t\leftrightarrow p$$

The textbook algorithms output vertices in counterclockwise order. Follow the lectures’ clockwise convention in exam answers unless told otherwise.

---

2.3 Divide and Conquer Plan

1. Sort points by $x$ coordinate once and for all: $O(n\lg n)$.
2. Divide $S$ into a left half $A$ and a right half $B$ by $x$ coordinate.
3. Recursively compute $CH(A)$ and $CH(B)$.
4. Merge the two hulls.

All the difficulty is in step 4.

---

2.4 Tangents

The merged hull keeps part of $CH(A)$, part of $CH(B)$, and two new bridging edges:

• upper tangent $(a_i,b_j)$: the bridge across the top,
• lower tangent $(a_k,b_m)$: the bridge across the bottom.

An upper tangent does not mean $a_i$ or $b_j$ is the highest point of its hull (Example A in the notes shows this).

---

2.5 Why the Two-Finger Search Works (Intuition Only)

$a_1$ is the rightmost point of $CH(A)$ and $b_1$ is the leftmost point of $CH(B)$. The search moves anticlockwise from $a_1$ and clockwise from $b_1$. If $(a_i,b_j)$ is a pair where moving either finger decreases $y(i,j)$, then no points lie above the line through $a_i$ and $b_j$.

The lectures state that the formal proof is involved and is not covered.

---

3. Main Governing Equations and Formulas

3.1 Brute Force

Test every segment between two points: it is a hull edge if all other points lie on one side of it.

$$O(n^2)\text{ segments}\times O(n)\text{ tests}=O(n^3)$$

Use as the baseline that divide and conquer beats.

---

3.2 Tangent Criterion

Let $L$ be the vertical line separating $A$ and $B$. Define

$$y(i,j)=\text{the }y\text{-coordinate where segment }(a_i,b_j)\text{ crosses }L$$

Claim from the lectures:

$$(a_i,b_j)\text{ is the upper tangent}\iff (i,j)\text{ maximizes }y(i,j)$$

If $y(i,j)$ is not maximal, there are points on both sides of $(a_i,b_j)$, so it cannot be a tangent. The lower tangent minimizes $y(i,j)$.

---

3.3 Naive Tangent Search

Check all $(a_i,b_j)$ pairs: $O(n^2)$ per merge.

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

Use to explain why the merge step must be linear.

---

3.4 Two-Finger Upper Tangent: $\Theta(n)$

$CH(A)=(a_1,\dots,a_p)$ with $a_1$ of maximum $x$; $CH(B)=(b_1,\dots,b_q)$ with $b_1$ of minimum $x$.

i = 1
j = 1
while (y(i, j+1) > y(i, j) or y(i-1, j) > y(i, j)):
    if y(i, j+1) > y(i, j):        # move right finger
        j = j + 1  (mod q)
    else:                          # move left finger
        i = i - 1  (mod p)
return (a_i, b_j) as upper tangent

Each finger only moves forward around its hull, so the loop runs $O(p+q)=O(n)$ times.

The lower tangent is found the same way, minimizing $y(i,j)$ with the fingers moving the other way.

---

3.5 Cut and Paste Merge: $\Theta(n)$

With upper tangent $(a_i,b_j)$ and lower tangent $(a_k,b_m)$:

1. Link $a_i$ to $b_j$.
2. Go down the $b$ list until you see $b_m$, and link $b_m$ to $a_k$.
3. Continue along the $a$ list until you return to $a_i$.

Lecture example: $CH(A)=(a_1,\dots,a_5)$, $CH(B)=(b_1,b_2,b_3)$, upper tangent $(a_4,b_2)$, lower tangent $(a_3,b_3)$, merged hull $(a_4,b_2,b_3,a_3)$.

---

3.6 Divide and Conquer Running Time

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

by case 2 of the master theorem. The one-time sort is also $O(n\lg n)$, so the total is $\Theta(n\lg n)$.

---

3.7 Textbook Alternative: Graham’s Scan, $O(n\lg n)$

1. Let $p_0$ be the point with minimum $y$ (leftmost on a tie). It is a hull vertex.
2. Sort the rest by polar angle counterclockwise around $p_0$ (keep only the farthest point for equal angles).
3. Push $p_0,p_1,p_2$ onto a stack.
4. For each next point $p_i$: while next-to-top, top, $p_i$ makes a nonleft turn, pop. Then push $p_i$.

The stack ends with the hull in counterclockwise order. Sorting is $O(n\lg n)$. The loop is $O(n)$ total by aggregate analysis: each point is pushed once, so it is popped at most once.

---

3.8 Textbook Alternative: Jarvis’s March, $O(nh)$

Gift wrapping: start at the lowest point; the next vertex has the smallest polar angle from the current one. Build the right chain up to the highest point, then the left chain back down.

$$O(nh),\quad h=\text{number of hull vertices}$$

Faster than Graham’s scan when $h=o(\lg n)$.

---

4. Problem-Solving Workflow

1. State the input assumptions (distinct $x$, distinct $y$, no three collinear) and the output format (clockwise linked list).
2. Pre-sort by $x$ once: $O(n\lg n)$.
3. Divide at the median $x$ into $A$ and $B$.
4. Recurse on both halves.
5. Find the upper tangent with the two-finger search (Section 3.4).
6. Find the lower tangent the same way.
7. Cut and paste the two hulls (Section 3.5).
8. Write $T(n)=2T(n/2)+\Theta(n)$ and solve it with the master theorem.
9. If asked about correctness, use the $y(i,j)$ criterion (Section 3.2) and the intuition in Section 2.5.

Practice: Problem Set 1, Problem 1-2 (radio stations within distance 1) uses the same pattern: presorted lists $L_x$ and $L_y$, divide and conquer, and an $O(n\lg n)$ target, so the combine step has to be linear.

---

5. Decision Rules / Decision Trees

5.1 Which Hull Algorithm?

Need the lecture algorithm or a D&C design? → divide and conquer, $\Theta(n\lg n)$

Need a simple stack-based method? → Graham’s scan, $O(n\lg n)$

Hull is known to have very few vertices ($h=o(\lg n)$)? → Jarvis’s march, $O(nh)$

Only asked for a baseline? → brute force, $O(n^3)$

5.2 Moving the Fingers (Upper Tangent)

$y(i,j+1)>y(i,j)$? → move right finger: $j=j+1 \pmod q$

Else $y(i-1,j)>y(i,j)$? → move left finger: $i=i-1 \pmod p$

Neither increases $y$? → stop, $(a_i,b_j)$ is the upper tangent

5.3 Merge Cost Decides the Total

Merge is $\Theta(n^2)$ (try all pairs)? → $T(n)=\Theta(n^2)$

Merge is $\Theta(n)$ (two fingers)? → $T(n)=\Theta(n\lg n)$

---

6. Important Tables / Correlations Needed

6.1 Algorithm Summary

Method	Idea	Time	Source
Brute force	test all segments	$O(n^3)$	lecture
D&C, naive merge	all tangent pairs	$\Theta(n^2)$	lecture
D&C, two-finger merge	linear tangent search	$\Theta(n\lg n)$	lecture
Graham’s scan	polar sort + stack	$O(n\lg n)$	textbook
Jarvis’s march	gift wrapping	$O(nh)$	textbook
Prune-and-search	discard a constant fraction	$O(n\lg h)$	textbook (mentioned only)

6.2 Merge Step Costs

Step	Cost
Find upper tangent	$\Theta(n)$
Find lower tangent	$\Theta(n)$
Cut and paste	$\Theta(n)$
Whole merge	$\Theta(n)$

---

7. Key Takeaways

• $CH(S)$ is the smallest polygon containing all points: the rubber band around the nails.
• The lectures store the hull clockwise in a doubly linked list; the textbook outputs counterclockwise.
• Brute force is $O(n^2)$ edges times $O(n)$ tests $=O(n^3)$.
• D&C: sort by $x$ once, split into halves, recurse, merge with two tangents.
• Upper tangent maximizes $y(i,j)$, the crossing height on the dividing line $L$.
• The upper tangent’s endpoints need not be the highest points.
• Two-finger search: right finger $j+1$, left finger $i-1$, stop when neither raises $y(i,j)$.
• Merge is $\Theta(n)$, so $T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)$.
• A $\Theta(n^2)$ merge would make the whole algorithm $\Theta(n^2)$.
• Textbook alternatives: Graham’s scan $O(n\lg n)$, Jarvis’s march $O(nh)$.