What Is a Convex Hull? The Geometry Concept Behind Erect the Fence

You have a map with twenty cities marked on it. You want the tightest possible boundary around all of them. Not a rectangle. Not a circle. Just the smallest polygon that wraps every city without wasting space. So you grab a rubber band, stretch it around all the pins, and let go. The rubber band analogy is mathematically exact: the convex hull of a set of points is the smallest convex polygon containing all of them.

Most engineers spend their careers happily ignoring this. Then LeetCode 587 shows up in their interview and the blissful ignorance ends.

The good news: understanding the concept makes the algorithm feel inevitable. The bad news: you need to understand it before the interview, not during. "I'll work out convex hulls live on the whiteboard" is a sentence that has never ended well.

What "Convex" Actually Means

A polygon is convex if you pick any two points inside it, draw a line segment between them, and that segment never exits the shape. No dents. No caves. No star shapes. No crescents.

A triangle is always convex. A regular hexagon is convex. The letter C is not convex, because you can draw a chord that exits the opening. Most of the interesting-looking geometric shapes you sketch under pressure during an interview are not convex, which is information you will discover at the wrong moment.

A set of points has infinitely many convex enclosures (a massive circle contains them all), but only one smallest one. That is the hull. The vertices of the hull are always a subset of the original input points. The algorithm never invents a new point. It selects from what you give it.

A Concrete Example First

Five points:

A = (1, 1)
B = (5, 1)
C = (3, 5)
D = (2, 2)
E = (4, 2)

A and B sit on the bottom, C is at the top, D and E are in the middle. The rubber band snaps around A, B, and C. That triangle is the hull. Points D and E are interior. They are inside the boundary and contribute nothing to it.

Add a sixth point at F = (0, 3) and the hull changes. F is outside the triangle, so the rubber band must stretch to include it. The hull becomes a quadrilateral: A, B, C, F. One outlier rewrites the entire shape.

Diagram showing the convex hull of points A, B, C, D, E where D and E are interior

The hull is sensitive to extreme points. Any vertex on the hull is extreme in at least one direction: there exists a line through it such that all other points sit on one side.

The One Check That Runs Everything

Here is the part that should make you feel slightly cheated by how simple it is.

Every convex hull algorithm, all of them, reduces to one primitive: detecting whether three consecutive points make a left turn or a right turn. That is the entire insight.

As you trace the hull counterclockwise, you always turn left. If three points make a right turn, the middle point is inside the hull and needs to go.

The tool is the 2D cross product. For three points P1, P2, P3:

def cross(p1, p2, p3):
    # positive = left turn, negative = right turn, zero = collinear
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - \
           (p2[1] - p1[1]) * (p3[0] - p1[0])

This computes the z-component of the 3D cross product when P1→P2 and P1→P3 are treated as vectors. The sign tells you which side of the directed line P1→P2 the point P3 falls on.

Walk through the example. A=(1,1), B=(5,1), C=(3,5):

cross(A, B, C) = (5-1)*(5-1) - (1-1)*(3-1) = 16

Positive. Left turn. C is on the correct side of A→B for a counterclockwise hull.

Now try A=(1,1), B=(5,1), D=(2,2):

cross(A, B, D) = (5-1)*(2-1) - (1-1)*(2-1) = 4

Also positive. D makes a left turn from A→B. But when C arrives later, D gets removed because it falls below the line from B to C. The cross product is evaluated dynamically as the stack grows. A point that survives two earlier comparisons can still get ejected when a farther point arrives.

One formula. One sign. Every convex hull algorithm in existence collapses into this check.

Ponytail: "He says nothing. He writes one line. It works." The cross product: one expression, one sign, and the entire convex hull problem becomes a stack of pop conditions.

Two Algorithms, Same Primitive

Graham Scan picks an anchor (the lowest point by y, ties broken by x), sorts all other points by polar angle relative to that anchor, then walks through the sorted list with a stack: if the new point creates a clockwise turn with the top two entries, pop the top; repeat until left-turning, then push. The scan itself is O(n) after sorting.

Monotone Chain (Andrew's Algorithm) sorts all points by x-coordinate, breaking ties by y. It builds the lower hull walking left to right, upper hull right to left, same stack logic both times. Most people find this easier because sorting by coordinate feels more intuitive than sorting by angle. The algorithm is the same. The traversal order is different.

Both produce the hull in counterclockwise order.

LeetCode 587 adds one wrinkle: collinear boundary points must be included. The default pop condition is cross(...) <= 0, which removes collinear points because zero gets treated as a non-left turn. To keep them, change it to cross(...) < 0. One character. A trivial fix if you understood the sign check, and an invisible gotcha if you memorized the algorithm without understanding why it works.

For full implementations across fourteen languages, the Convex Hull Algorithm guide covers every detail.

Why You Cannot Beat O(n log n)

The sorting step dominates. Sorting n points costs O(n log n). The stack traversal is O(n) because each point is pushed and popped at most once.

You might be tempted to look for something faster. There is a classical reduction that closes this off: if you could compute the convex hull faster than O(n log n), you would have a sub-O(n log n) comparison-based sort. Sorting has an information-theoretic lower bound of Ω(n log n) from the decision tree argument, so convex hull inherits that floor. O(n log n) is provably optimal for comparison-based convex hull. The proof is not negotiable.

Computer scientists celebrating finding an O(n) sort that uses Omega(n!) space You, arriving at your "faster" convex hull algorithm. The lower bound proof has been waiting.

Space is O(n): the output hull has at most n vertices, and the stack holds at most n entries at any moment.

One nuance worth flagging: Jarvis March (Gift Wrapping) runs in O(nh), where h is the number of hull points. When h is tiny relative to n, this beats O(n log n). Chan's Algorithm achieves the optimal O(n log h) but is significantly more complex and not expected in any interview. State O(n log n) time, O(n) space, and note the sorting step dominates. That is the correct answer.

The comparison sort lower bound post explains the decision tree argument in full if you want the proof.

Where Convex Hull Shows Up in Your Interview

Standard SWE loops at Google, Meta, and Amazon almost never ask for a convex hull directly. The word "almost" is doing a lot of work in that sentence.

LeetCode Hard problems: 587 (Erect the Fence) is the main one. It is labeled Hard and most candidates cannot attempt it without having seen the algorithm before. The problem asks you to find the minimum perimeter fence around a set of trees. That description sounds reasonable until you realize the entire thing is a convex hull problem in disguise. Seeing that connection is the hard part. Everything after it follows from the algorithm.

Competitive programming: Codeforces Div 1 and Div 2, IOI, and ACM-ICPC use convex hulls as subroutines regularly. Problems about minimum perimeter, extreme projections, or rotating calipers often require building a hull first and doing something with it second.

Quant and HFT interviews: Jane Street, Citadel, and DE Shaw mix algorithmic reasoning with mathematical thinking. Geometry problems appear more often here than in standard SWE loops. The quant and HFT coding interview problems guide covers the broader landscape.

Hidden in other problems: Occasionally a problem about "finding the outermost boundary" or "detecting which points dominate all others" is a convex hull in disguise. Recognition is the skill.

What the Interviewer Is Actually Scoring

On the rare occasion a convex hull problem appears, the interviewer is testing two things.

First, pattern recognition. Seeing a coordinate geometry problem and reaching for a convex hull requires knowing the geometric structure of what you are looking at. You cannot derive this on the spot. You have to have encountered convex hulls before. This is why knowing the concept matters beyond the immediate problem.

Second, understanding the cross product. You should be able to explain what the sign means and why the pop condition works. Pasting code from memory and fumbling when asked about the < 0 check is a weak signal. Reconstructing the cross product from first principles (two vectors, z-component of the 3D cross product, positive equals left turn) is a strong one.

If you freeze mid-interview, sketch the rubber band picture on the whiteboard. Walk through a three-point example with concrete numbers. The algorithm follows naturally from the geometry once you can see it.

Practicing that kind of verbal reasoning under timed pressure is where SpaceComplexity helps: voice-based mock interviews with rubric-based feedback on communication and problem-solving, not just whether the code compiled.

The Short Version

The convex hull is the smallest convex polygon enclosing a set of points. The rubber band analogy is exact.
Hull vertices are always a subset of the original input. The algorithm selects, never invents.
The fundamental primitive is the cross product, which detects left vs right turns. Counterclockwise traversal always turns left.
Both Graham Scan and Monotone Chain run in O(n log n) because of sorting, which is also the theoretical lower bound.
LeetCode 587 requires keeping collinear boundary points, changing the pop condition from <= 0 to < 0. One character. Easy to miss.
Convex hull is niche for standard SWE loops and expected knowledge for competitive programming and quant interviews.

For the full algorithm walkthrough with code in every language, see the Convex Hull Algorithm deep-dive.