Decide what the hull routine must return
A convex hull is a geometric set, but a program must return a finite representation. Should points in the middle of a straight boundary edge be included? Should the first vertex appear again at the end? What happens if every point lies on one line? These are output choices that must be fixed before a turn test becomes a correct algorithm.
We will return only extreme vertices, and use a grouped-x monotone-chain construction. A lower boundary and an upper boundary are built separately. Grouping points with the same x-coordinate makes vertical edges explicit, while each scan deals with strictly monotone x-coordinates.
Specify geometry, arithmetic and degeneracies
Definition 8.3.1
(Convex hull and extreme-vertex output)
For a finite point set P, its convex hull consists of all convex combinations of points in P: weighted sums with nonnegative weights whose sum is one. An extreme vertex cannot be written as a convex combination of other points in the set. Duplicated coordinates represent one geometric point.
The routine's output contract is:
- No points: return an empty list.
- One distinct point: return that point once.
- Several distinct collinear points: return the two segment endpoints.
- Otherwise: return the hull's extreme vertices counterclockwise, starting at the lexicographically smallest point, with no repeated closing vertex and no extra collinear points along an edge.
Use ordinary Cartesian coordinates, with y increasing upward. Lexicographic order compares x first and then y. We assume exact coordinate comparison and arithmetic, as with appropriately implemented integer or rational data. The sign of an orientation determinant is part of this contract; a floating-point rounding error is not justified by the proof below.
For points a,b,c define
A positive value means a left turn, a negative value a right turn, and zero means collinearity when a and b are distinct. The scans will have distinct x-coordinates, so the edge direction is never zero. This lesson uses the orientation predicate; segment-intersection algorithms are a separate topic.
One x-column contributes at most two boundary endpoints
For each distinct x-coordinate, keep its lowest point as a lower-chain candidate and its highest point as an upper-chain candidate. A point strictly between them on the same vertical line is a convex combination of those two and cannot be extreme.
More specifically, a point above the column minimum cannot be on the lowest boundary at that x; the symmetric statement holds for the upper boundary. At the leftmost and rightmost x, the minimum and maximum may both be vertices, forming a vertical hull edge. Thus we retain both candidates rather than discard a whole end edge.
If there is only one distinct x-coordinate, all points lie on a vertical segment; its bottom and top endpoints already solve the problem. Otherwise the lower candidates have strictly increasing x, and the upper candidates are scanned in strictly decreasing x.
The scan removes a middle point on a non-left turn
SCAN_CHAIN(points_in_scan_order):
stack = empty list
for q in points_in_scan_order:
while length(stack) >= 2 and orient(stack[-2], stack[-1], q) <= 0:
remove last point from stack
append q to stack
return stack
The retained consecutive triples make strict left turns. For an
increasing-x scan, this is the same as strictly increasing edge slopes.
The <= 0 choice discards collinear middle points, matching our
extreme-vertex contract.
Theorem 8.3.2
(A popped lower candidate is not an extreme lower vertex)
Suppose increasing-x candidates satisfy and . The middle point b lies on or above the chord from a to q. It cannot be an extreme vertex of the lower boundary of the full input hull.
Proof
(The chord is already a witness inside the eventual hull)
Let , so . The chord point has the same x-coordinate as b. Direct expansion gives
Thus the nonpositive turn gives . If the inequality is strict, z is a point of the hull strictly below b at that x, so b is not on the lower boundary. If equality holds, b is an interior convex combination of distinct a,q and is not extreme.
Both a and q are input points, so their chord stays inside the final hull even if a or q is later removed from this scan. The certificate therefore remains valid after more points are processed.
A pop is a statement about this boundary. A point removed from the lower scan can still be an upper hull vertex. The two scans must not share a global flag saying that a popped input point is useless.
Why the retained lower chain is exactly the lower hull
Theorem 8.3.3
(The scan returns exactly the lower extreme vertices)
Let the lower candidates have strictly increasing -coordinates. Then SCAN_CHAIN returns, in increasing order, exactly the extreme vertices of the lower boundary of their convex hull, including its two end vertices.
Proof
(Combine a removal certificate with the convex-chain invariant)
The stack is always in increasing x order. After the while loop, its last new triple is a strict left turn, while earlier retained triples are unchanged. Induction therefore gives a chain with strictly increasing slopes after every insertion.
No true extreme vertex of the final lower hull is ever lost: grouping keeps every possible lower vertex, and the pop certificate forbids removing one. The first and last lower candidates are also retained, so the stack includes both lower end vertices.
It remains to exclude extra vertices. Consider consecutive true extreme lower vertices a,c. The true lower boundary between them is their straight edge, and every input point with an intermediate x lies on or above this edge. A chain with increasing slopes lies on or below the chord joining any two of its vertices: its average slope before an intermediate point is at most its average slope afterward, which is equivalent to this chord inequality.
The retained chain contains a,c, so any of its intermediate vertices would have to be both on/above their true hull edge and on/below their chord. It must lie on that edge. Strictly increasing slopes exclude an extra collinear middle vertex. Thus the retained vertices are exactly the lower extreme vertices, joined in order.
Proof X-ray
Nothing true is lost and nothing extra is kept
The proof joins two separate guarantees. The removal certificate says that a pop never discards a true lower vertex; it needs strictly increasing , because the chord construction divides by , which vanishes if two candidates share an -coordinate. The convex-chain invariant says that the retained chain has strictly increasing slopes; it is the pop condition <= 0, not < 0, that makes the slopes strict and so excludes a collinear middle vertex. The non-routine step is the chord inequality: a chain with increasing slopes lies on or below the chord of any two of its vertices, while every input point lies on or above a true hull edge. An extra vertex between true vertices would therefore be squeezed onto the edge, where strict slopes forbid it. The argument closes because the first and last candidates are never popped, so the end vertices are present.
The upper proof follows by mapping to . This rotation turns upper column maxima into lower column minima, reverses x order, and preserves orientation because its determinant is positive. Therefore the same left-turn scan, applied to upper candidates from right to left, yields exactly the upper boundary.
Concept lensAnalytic
The lower hull as the largest convex function under the points
Let be the largest convex function on with at every lower candidate. Its graph is the lower boundary of the hull, and is piecewise linear. The extreme lower vertices are the two end points and the points where the slope of strictly increases. That is the scan's invariant read as a function: strictly increasing slopes, so a collinear middle point is not a breakpoint.
Join the boundaries without repeating endpoints
EXTREME_HULL(input_points):
P = lexicographically sorted distinct input points
if length(P) <= 1:
return P
lower_candidates = empty list
upper_candidates = empty list
for each group of P with one common x-coordinate:
append its minimum-y point to lower_candidates
append its maximum-y point to upper_candidates
if length(lower_candidates) == 1:
return [lower_candidates[0], upper_candidates[0]]
lower = SCAN_CHAIN(lower_candidates)
upper = SCAN_CHAIN(reverse(upper_candidates))
hull = empty list
for p in lower followed by upper:
if hull is empty or p != hull[-1]:
append p to hull
if length(hull) > 1 and hull[0] == hull[-1]:
remove last point from hull
return hull
When lower and upper endpoints coincide, the join removes the repeated point. When they differ at an end x, the connecting vertical segment is a real hull edge and both endpoints remain. All points lie between the exact lower and upper boundaries. Traversing lower left-to-right, then upper right-to-left, keeps that region on the left, giving the counterclockwise order in the noncollinear case.
With nonvertical collinear input, each scan contains just its two end points. The join removes repeated endpoints and returns two points; it does not pretend that a segment is a counterclockwise polygon. The one-column branch handles the vertical case, and deduplication handles an input consisting of many copies of one point.
Worked example 8.3.4
(A grid returns its corners, not every boundary sample)
Take all nine points with , and one additional copy of (0,0). The three column minima are (0,0),(1,0),(2,0), while the maxima are (0,2),(1,2),(2,2).
The lower scan removes (1,0) on a zero turn. The reverse upper scan removes (1,2) similarly. Joining yields (0,0),(2,0),(2,2),(0,2). Points (0,1),(2,1) were excluded by the column grouping, and (1,1) was not a boundary candidate. The duplicate (0,0) appears once.
The output's filled polygon is the hull of all input points. Returning four vertices does not mean that only four input points lie on its boundary; it means only four are extreme.
Worked example 8.3.5
(A lower pop can still be an upper vertex)
Use points (0,0),(1,2),(2,0),(3,1). When (2,0) arrives in the lower scan, the turn through (1,2) is , so that middle point is removed. The lower chain finishes as (0,0),(2,0),(3,1).
The upper scan retains (3,1),(1,2),(0,0), so the full hull is (0,0),(2,0),(3,1),(1,2). Point (1,2) was excluded from the lower boundary for a valid reason, yet is still an extreme vertex of the entire hull. Removing it globally would be incorrect.
Worked example 8.3.6
(A vertical edge on the left)
Take the points , and . The column contributes the lower candidate and the upper candidate ; the column contributes to both lists. The lower scan has only two points and returns . The reversed upper list is , which returns . In the join, the repeated is dropped, giving , and since no closing point is removed. Here , so the order is counterclockwise, and the closing edge from back to is the vertical hull edge. Keeping both candidates of the end column is what preserves that edge.
Common mistake
(Skipping deduplication of repeated points)
For five copies of the point there is one -column, so the one-column branch returns the lowest and highest point of that column, which are both . Without deduplication the output would list the same point twice instead of once. Deduplicate after sorting, before grouping.
Common mistake
(Treating a pop as global)
A point popped from the lower scan is only excluded from the lower boundary. In the example the point is popped from the lower scan but is an extreme vertex of the whole hull. Marking it as useless for the upper scan would lose a hull vertex.
The scan is linear even though a while loop is nested
Proposition 8.3.7
(Linear cost of one scan)
A scan over candidates performs at most orientation tests and pushes, so it takes time.
Proof
(Pops are paid for by pushes)
Every candidate is pushed once. Once popped from one scan, it never re-enters that scan, so the total number of pops is at most the number of pushes. Each successful while test pays for a pop; each new point can cause at most one final failed test before its push. Thus each scan takes linear time in its candidate count.
For N input entries, sorting/deduplicating costs comparisons, grouping and joining take , and both scans together take . The implementation stores sorted points, candidates and stacks, using space. These counts assume constant-cost exact coordinate comparisons and orientation arithmetic; large-integer bit costs must be charged separately.
Counterexample mode
Changing one inequality does not change the whole output contract
One might change the pop condition to < 0 to retain collinear
points. In this grouped-x algorithm, that would still not retain
all boundary points: (0,1) in the grid example was removed by
grouping before any turn test.
An all-boundary-points API needs a different handling of vertical columns, collinear runs and degenerate joins. Our proved API returns extreme vertices. A different comparison sign alone does not establish a different contract for the complete pipeline.
Solved exercises
Quick check
(Let , , . Compute the orientation, identify the chord point below at the same , and state exactly what the pop proves. Does it prove that can never be in the full hull?)
Use the formula .
Solution · Answer
The determinant is . At x=1, the chord from a to q contains z=(1,0), strictly below b. Thus b cannot be a lower boundary vertex once a,q are in the data. It can still be an upper extreme vertex, as the second worked example demonstrates. The certificate is boundary-specific.
Quick check
(Give the output for no points, for five copies of , and for with duplicates allowed. Also give the output for . Which outputs have a counterclockwise order?)
Apply the output contract case by case.
Solution · Answer
The outputs are an empty list; [(2,3)]; [(2,-1),(2,4)]; and [(0,0),(3,3)]. Deduplication solves the repeated point, the one-column branch solves the vertical segment, and zero-turn pops remove nonvertical collinear middle points. None of these is a nondegenerate polygon, so no counterclockwise polygon order is asserted.
Quick check
(Suppose a newly added point causes ten candidates to be popped. Why can this happen without invalidating the linear scan bound? What cost still dominates when input points arrive unsorted?)
Count pushes and pops over the whole scan.
Solution · Answer
Those ten pops remove ten distinct candidates previously pushed into that scan. They cannot be popped again there. Across the entire scan, total pops are at most total pushes, so summing all iterations gives linear work despite one expensive iteration. Sorting the unsorted input still costs comparisons in this implementation; the linear stack phase does not remove that cost.
Quick check
(Input points are . A program returns the rectangle , arguing that it is convex and contains every input. Is this the hull? Give the actual extreme-vertex output and explain the missing justification.)
Is every vertex of the rectangle an input point?
Solution · Answer
The actual output is (0,1),(1,0),(2,1),(1,2), a diamond in counterclockwise order. The rectangle is a strictly larger convex superset; for example (0,0) is outside the diamond and is not an input vertex. Convexity plus containment proves only one inclusion. Our proof also identifies the exact lower/upper boundaries and uses input vertices, which makes the returned polygon contained in the input convex hull. Both inclusions are needed for equality.