The Central Idea
Let
\[ S=\{P_1,P_2,\ldots,P_n\} \]be a finite set of points.
The convex hull of \(S\), written
\[ \operatorname{conv}(S), \]is the smallest convex set containing every point of \(S\).
In the plane, the boundary of the hull is usually a convex polygon whose vertices are selected from the original point set.
What Does Convex Mean?
A set is convex if every segment joining two points of the set remains entirely inside the set.
If \(A\) and \(B\) belong to a convex set, then every point
\[ (1-t)A+tB \]with
\[ 0\le t\le1 \]also belongs to the set.
The Rubber-Band Picture
Imagine placing nails at the input points and stretching a rubber band around all of them.
When released, the band contracts until it touches only the outermost points.
The polygon traced by the band is the convex hull.
Interior points do not affect the hull boundary.
Hull Vertices Are Extreme Points
A point on a hull vertex is an extreme point.
It cannot be written as a strict convex combination of the other points in the set.
Geometrically, there is a supporting line through that point with all other points lying on one side.
Interior Points Do Not Change the Hull
Suppose a point \(P\) lies strictly inside the convex hull of the other points.
Removing \(P\) does not change the hull:
\[ \boxed{ \operatorname{conv}(S) = \operatorname{conv}(S\setminus\{P\}) }. \]Convex hull algorithms therefore seek the relatively small subset of boundary points that determines the outer shape.
The Hull Boundary Has an Order
A convex hull is not merely an unordered set of extreme points.
For most geometric uses, the vertices should be listed cyclically:
\[ H_0,H_1,\ldots,H_{h-1}. \]They are usually stored in clockwise or counterclockwise order.
Here \(h\) denotes the number of hull vertices.
Orientation Is the Fundamental Predicate
For three points \(A\), \(B\), and \(C\), compute
\[ \boxed{ \operatorname{orient}(A,B,C) = (x_B-x_A)(y_C-y_A) - (y_B-y_A)(x_C-x_A) }. \]Under the usual Cartesian orientation:
- positive means a counterclockwise turn;
- negative means a clockwise turn;
- zero means collinear.
Nearly every standard planar convex hull algorithm depends on this test.
Why Turns Matter
If hull vertices are being built counterclockwise, the boundary should not make an inward clockwise turn.
A candidate sequence
\[ A\to B\to C \]with
\[ \operatorname{orient}(A,B,C)<0 \]bends inward relative to a counterclockwise convex boundary.
Many hull algorithms remove such points as they construct the boundary.
The Smallest Possible Inputs
Degenerate inputs should be classified explicitly.
- An empty point set has no hull.
- One distinct point has a one-point hull.
- Two distinct points have a segment as their hull.
- Three noncollinear points have a triangular hull.
General algorithms should either handle these cases directly or define a consistent output convention.
All Points Collinear
If every point lies on the same line, the convex hull is not a two-dimensional polygon.
The geometric hull is the segment joining the two extreme endpoints.
Depending on the desired output, an implementation may return:
- only the two extreme endpoints;
- all boundary points in sorted order.
The convention should be chosen deliberately.
Duplicate Points
Repeated coordinates do not create new geometry.
Many hull algorithms simplify the input by removing duplicate points before processing.
This prevents repeated vertices and unnecessary orientation tests.
Finding an Extreme Starting Point
A common starting vertex is the point with smallest \(x\)-coordinate.
If several points share that value, use the one with smallest \(y\)-coordinate.
Such a point must lie on the convex hull because no point exists farther to its left.
Gift Wrapping
The gift-wrapping algorithm, also called Jarvis march, builds the hull one edge at a time.
Starting from a known hull point, it searches all remaining points for the next point that gives the most extreme turn around the set.
The process continues until it returns to the starting point.
The Gift-Wrapping Picture
Imagine rotating a directed line around the current hull point.
The next hull point is the first point encountered as the line sweeps around the outside of the point set.
Repeating this motion wraps the boundary around the point cloud.
Choosing the Next Gift-Wrapping Point
Suppose \(P\) is the current hull point.
Begin with some candidate \(Q\ne P\).
For every other point \(R\), compare
\[ \operatorname{orient}(P,Q,R). \]If \(R\) lies farther to the outside than \(Q\) under the chosen orientation convention, replace \(Q\) by \(R\).
After scanning all points, the final \(Q\) is the next hull vertex.
Collinear Candidates in Gift Wrapping
Suppose several points are collinear in the direction of the next hull edge.
If only extreme hull vertices are desired, choose the farthest collinear point.
Otherwise, an interior point on that edge could incorrectly become a hull vertex and force later cleanup.
Gift-Wrapping Complexity
If there are \(n\) input points and \(h\) hull vertices, gift wrapping scans the point set once for each hull edge.
Its running time is therefore
\[ \boxed{O(nh)}. \]This can be attractive when the hull contains relatively few points.
Output-Sensitive Algorithms
Gift wrapping is called output-sensitive because its running time depends on the output size \(h\) as well as the input size \(n\).
A point set with millions of interior points but only a small number of hull vertices may therefore behave differently from a set in which most points lie on the hull.
Graham Scan
Graham scan follows a different strategy.
- Choose an extreme pivot point.
- Sort the other points by polar angle around the pivot.
- Process them in angular order.
- Maintain a stack of candidate hull vertices.
- Remove points whenever the boundary makes an inward turn.
Choosing a Graham-Scan Pivot
A standard choice is the point with smallest \(y\)-coordinate.
If several points share that value, choose the one with smallest \(x\)-coordinate.
This point is guaranteed to lie on the hull and provides a consistent reference for angular sorting.
Polar-Angle Ordering
After choosing pivot \(P_0\), each other point \(P\) has a direction
\[ P-P_0. \]Graham scan processes these directions in increasing polar angle.
Conceptually, this rotates a ray around the pivot and encounters the points in directional order.
Angles Need Not Be Computed Explicitly
An implementation does not necessarily need to compute
\[ \theta=\operatorname{atan2}(y-y_0,x-x_0) \]for every point.
Orientation tests and quadrant information can compare directions without evaluating trigonometric functions.
This is another example of replacing a geometric quantity with a simpler predicate.
The Graham-Scan Stack
Suppose the current stack ends with points
\[ A,\ B \]and the next sorted point is \(C\).
For a counterclockwise hull, inspect
\[ \operatorname{orient}(A,B,C). \]If the result represents an unacceptable clockwise turn, remove \(B\) and test again with the new top of the stack.
Why Removing an Inward Point Is Safe
If the ordered path
\[ A\to B\to C \]makes an inward turn, then \(B\) cannot remain an extreme vertex of the convex outer boundary between \(A\) and \(C\).
Removing \(B\) restores the possibility of a convex boundary.
Graham-Scan Complexity
The scan itself is linear after sorting because each point is pushed onto and popped from the stack only a limited number of times.
The angular sort dominates the running time:
\[ \boxed{O(n\log n)}. \]Monotone Chain
Another widely used hull algorithm is the monotone chain method, often associated with Andrew's algorithm.
It avoids polar-angle sorting.
Instead, it sorts points lexicographically by coordinate and constructs:
- a lower hull;
- an upper hull.
The two chains are then joined.
Lexicographic Sorting
Sort points primarily by \(x\), and use \(y\) to break ties:
\[ (x_1,y_1)<(x_2,y_2) \]when either
\[ x_1Building the Lower Hull
Process the sorted points from left to right.
Maintain a list of candidate lower-hull vertices.
Whenever the last two vertices and the new point make an unacceptable turn, remove the middle vertex.
Continue until adding the new point preserves convexity.
Building the Upper Hull
Process the same sorted points in reverse order.
Apply the same turn logic to build the upper chain.
The lower and upper chains share their leftmost and rightmost endpoints, so duplicate endpoint copies are removed before concatenation.
Monotone-Chain Complexity
Sorting requires
\[ O(n\log n) \]time.
The two scans together require only linear time.
Therefore,
\[ \boxed{O(n\log n)} \]is the overall complexity.
Why Monotone Chain Is Popular
Monotone chain is often attractive because it uses:
- ordinary coordinate sorting;
- the same orientation predicate already used elsewhere;
- a simple stack-like construction;
- straightforward handling of duplicates.
It is one of the most practical general-purpose planar hull algorithms.
Whether to Keep Collinear Boundary Points
Suppose three consecutive boundary points satisfy
\[ \operatorname{orient}(A,B,C)=0. \]An implementation must decide whether \(B\) should remain in the hull output.
There are two common conventions:
- return only extreme corner vertices;
- return every input point lying on the hull boundary.
The orientation inequality in the scan changes according to this choice.
Strict and Non-Strict Turn Tests
A lower-hull construction might remove points while
\[ \operatorname{orient}(A,B,C)\le0 \]if collinear interior edge points should be discarded.
It might instead remove only when
\[ \operatorname{orient}(A,B,C)<0 \]if collinear boundary points should be retained.
This small inequality choice changes the output convention.
Example Point Set
Consider
\[ S= \{ (0,0), (1,1), (2,0), (2,2), (0,2), (1,\tfrac12) \}. \]The points
\[ (1,1) \]and
\[ (1,\tfrac12) \]lie inside the square determined by the four corner points.
They do not appear as convex hull vertices.
Hull of the Example
The convex hull vertices are
\[ \boxed{ (0,0), (2,0), (2,2), (0,2) }. \]In counterclockwise order, these points form the boundary of the smallest convex region containing the entire input set.
Verifying Convexity
Suppose a candidate hull is listed counterclockwise.
For every three consecutive vertices
\[ H_i,H_{i+1},H_{i+2}, \]check that the turns are consistent with convexity.
Under a strict counterclockwise convention:
\[ \boxed{ \operatorname{orient} (H_i,H_{i+1},H_{i+2})>0 } \]for every noncollinear corner.
Verifying Containment
A candidate hull must contain every input point.
Since the hull is convex, each input point can be tested against the interior half-planes of the hull edges.
A convex candidate that excludes even one input point is not a valid hull.
Verifying Minimality
Convexity and containment alone do not guarantee that a candidate boundary is the smallest possible convex set.
A true hull boundary is supported by extreme input points.
If a listed vertex lies strictly inside the convex polygon formed by the other listed vertices, it is unnecessary and the output is not minimal.
Hull Edges Are Supporting Edges
For each directed hull edge, all input points lie on the same side or on the supporting line.
For a counterclockwise hull edge from \(A\) to \(B\),
\[ \boxed{ \operatorname{orient}(A,B,P)\ge0 } \]for every input point \(P\), under the usual orientation convention.
Convex Combinations
The convex hull can also be defined algebraically.
A point \(X\) belongs to the convex hull of
\[ P_1,\ldots,P_n \]if it can be written
\[ \boxed{ X= \lambda_1P_1+\cdots+\lambda_nP_n } \]where
\[ \lambda_i\ge0 \]and
\[ \lambda_1+\cdots+\lambda_n=1. \]Why the Algebraic Definition Matters
The convex-combination definition extends naturally beyond two dimensions.
It also reveals that the convex hull is not merely a boundary polygon.
The hull includes every point in the filled convex region generated by the input points.
Hull Area
Once the hull vertices are ordered cyclically, its area can be computed using the shoelace formula.
For vertices
\[ (x_0,y_0),\ldots,(x_{h-1},y_{h-1}), \]the area is
\[ \boxed{ A= \frac12 \left| \sum_{i=0}^{h-1} \left( x_i y_{i+1}-y_i x_{i+1} \right) \right| } \]with indices taken cyclically.
Hull Perimeter
The perimeter is the sum of edge lengths:
\[ \boxed{ L= \sum_{i=0}^{h-1} \|H_{i+1}-H_i\| }. \]Once the hull is known, global size measures become much easier to compute.
Diameter of a Point Set
The farthest pair of points in a finite planar set must lie on the convex hull.
Therefore, interior points can be discarded before searching for the diameter.
This is a major reason convex hulls are useful as a preprocessing step.
Bounding and Collision Applications
A convex hull can serve as a compact outer approximation of a more detailed object.
This can simplify:
- broad-phase collision tests;
- visibility calculations;
- spatial indexing;
- shape comparison;
- graphics and physical simulation.
Convex Hulls in Mapping and Data Analysis
Given spatial observations, a hull can summarize the outer extent of the sample.
Examples include:
- approximate geographic extent;
- outer boundary of measured locations;
- range envelopes;
- cluster summaries;
- initial regions for later spatial processing.
A convex hull may include empty space between observations, so it should not automatically be interpreted as the exact occupied region.
Convex Hulls Can Overgeneralize Shape
Because the hull must remain convex, it fills inward dents and gaps.
A crescent-shaped or U-shaped point distribution can therefore have a hull containing substantial area with no sample points.
Convex hulls summarize outer extent, not concave detail.
Higher-Dimensional Convex Hulls
In three dimensions, the convex hull of a finite point set is generally a convex polyhedron.
In higher dimensions, it becomes a convex polytope.
The central idea remains the same:
\[ \boxed{ \text{smallest convex set containing the input points} }. \]Numerical Robustness
Hull algorithms make discrete decisions from orientation signs.
A tiny numerical error can incorrectly classify three nearly collinear points as clockwise or counterclockwise.
Such an error can alter the combinatorial structure of the hull.
Near-Collinear Points
If
\[ |\operatorname{orient}(A,B,C)| \]is very small, the points are nearly collinear.
A floating-point implementation may use a tolerance, higher precision, or an exact orientation predicate depending on the reliability required.
Exact Predicates Can Protect Hull Structure
Since orientation is a sign test, exact or adaptive arithmetic can be used to determine whether the determinant is truly positive, negative, or zero.
This is especially valuable when:
- coordinates are large;
- points are nearly collinear;
- topological consistency matters;
- the hull feeds later geometric algorithms.
Sorting and Stability
Sorting is a major step in Graham scan and monotone chain.
Tie rules should be explicit for points sharing:
- the same coordinates;
- the same polar direction;
- the same \(x\)-coordinate;
- the same \(y\)-coordinate.
Deterministic tie handling makes the hull output reproducible.
Common Error: Keeping Interior Points as Hull Vertices
A hull vertex must contribute to the outer convex boundary.
A point strictly inside the polygon formed by other hull vertices should not remain in the hull output.
Orientation-based scan algorithms remove such candidates automatically.
Common Error: Ignoring Collinear Tie Cases
Several points may lie on the same hull edge.
If the implementation does not define whether to keep all boundary points or only edge endpoints, results can become inconsistent.
The desired output convention should determine the collinear comparison rule.
Common Error: Sorting by Slope
Slope can be inconvenient for angular ordering because vertical directions require division by zero and directions in different quadrants can share related slope values.
Polar-angle ordering or orientation-based comparison is generally more reliable.
Common Error: Forgetting to Remove Duplicate Endpoints
In monotone chain, the lower and upper hulls both contain the extreme leftmost and rightmost points.
If the chains are concatenated without removing repeated endpoint copies, the final cyclic boundary contains duplicates.
Common Error: Assuming Every Turn Must Be Strict
Whether a collinear boundary point should be removed depends on the output specification.
Using
\[ <0 \]versus
\[ \le0 \]in the orientation condition can change which collinear points survive.
Common Error: Using a Hull as an Exact Shape Boundary
A convex hull fills concavities.
It should not be treated as an exact reconstruction of a concave object or sampled region unless convexity is independently justified.
A Reliable Procedure for Gift Wrapping
- Remove duplicate points if appropriate.
- Handle zero-, one-, and two-point inputs directly.
- Choose a guaranteed extreme starting point.
- At the current hull point, scan every point for the most extreme next direction.
- Resolve collinear ties according to the hull-output convention.
- Add the selected point to the hull.
- Repeat until the algorithm returns to the start.
- Verify orientation and containment if needed.
A Reliable Procedure for Graham Scan
- Remove duplicates.
- Choose an extreme pivot.
- Sort the remaining points by polar direction around the pivot.
- Resolve equal-angle points consistently.
- Initialize the hull stack.
- Process sorted points in order.
- Pop while the latest turn violates the convexity convention.
- Push the new point.
- Return the resulting cyclic boundary.
A Reliable Procedure for Monotone Chain
- Remove duplicate points.
- Sort lexicographically by \(x\), then \(y\).
- Build the lower hull from left to right.
- Remove the latest point whenever the turn violates the chosen convexity rule.
- Build the upper hull from right to left.
- Remove duplicated extreme endpoints before concatenating the chains.
- Return the hull in cyclic order.
- Check special cases such as complete collinearity.
Choosing a Hull Algorithm
No single hull algorithm is best in every setting.
- Gift wrapping is conceptually simple and output-sensitive.
- Graham scan is classical and efficient after angular sorting.
- Monotone chain is simple to implement with ordinary coordinate sorting.
The best choice depends on input size, expected hull size, numerical requirements, existing data order, and implementation context.
Practice 1: Identify Interior Points
Consider
\[ S= \{ (0,0), (4,0), (4,4), (0,4), (2,2) \}. \]Which point is not a hull vertex?
Practice 2: Small Input
What is the convex hull of
\[ \{(1,2),(5,2)\}? \]Practice 3: Collinear Input
If the point set is
\[ \{(0,0),(1,0),(3,0),(5,0)\}, \]what is the geometric convex hull?
Practice 4: Orientation
Compute
\[ \operatorname{orient} \bigl((0,0),(3,0),(2,4)\bigr) \]and classify the turn.
Practice 5: Inward Turn
A counterclockwise hull construction currently ends with
\[ A=(0,0),\qquad B=(2,2), \]and considers
\[ C=(4,1). \]Compute the orientation and decide whether \(B\) can remain as the middle point of a counterclockwise convex turn.
Practice 6: Gift-Wrapping Complexity
A point set contains \(n=1000\) points and its hull contains \(h=10\) vertices.
What asymptotic work does gift wrapping perform?
Practice 7: Graham-Scan Complexity
What step dominates the asymptotic running time of Graham scan?
Practice 8: Monotone Chain
What are the two boundary pieces constructed by monotone chain?
Practice 9: Collinear Boundary Convention
Three points \(A,B,C\) lie on the same hull edge, with \(B\) between \(A\) and \(C\).
If the output should contain only extreme corners, should \(B\) remain?
Practice 10: Hull as Shape Approximation
Why can a convex hull be a poor exact representation of a strongly concave point distribution?
Practice Answers
Practice 1
The four corner points form a square.
The point
\[ \boxed{(2,2)} \]lies strictly inside and is not a hull vertex.
Practice 2
With two distinct points, the hull is the segment joining them:
\[ \boxed{ \overline{(1,2)(5,2)} }. \]Practice 3
All points are collinear, so the geometric hull is the segment joining the extreme endpoints:
\[ \boxed{ \overline{(0,0)(5,0)} }. \]Practice 4
\[ \operatorname{orient} = 3(4)-0(2) = 12. \]Since the result is positive,
\[ \boxed{\text{the turn is counterclockwise}.} \]Practice 5
\[ \operatorname{orient}(A,B,C) = 2(1)-2(4) = 2-8 = -6. \]The turn is clockwise, so under a counterclockwise hull construction,
\[ \boxed{B\text{ must be removed from that candidate turn}.} \]Practice 6
Gift wrapping performs
\[ O(nh). \]Here that is proportional to
\[ 1000\cdot10=10000 \]point examinations up to constant factors.
Practice 7
The angular sorting step dominates, giving
\[ \boxed{O(n\log n)}. \]Practice 8
Monotone chain constructs
\[ \boxed{\text{a lower hull and an upper hull}}. \]Practice 9
No. If only extreme corners are desired, the middle collinear point is unnecessary.
\[ \boxed{B\text{ should be omitted}.} \]Practice 10
A convex hull fills all inward dents because the hull must remain convex.
It can therefore contain substantial empty area that is not part of the actual concave distribution.
What to Remember
A convex hull extracts the outer convex structure of a point set.
- the hull is the smallest convex set containing all input points;
- interior points do not affect the hull boundary;
- orientation tests determine whether candidate turns preserve convexity;
- gift wrapping constructs hull edges one at a time in \(O(nh)\) time;
- Graham scan sorts by direction and then removes inward turns;
- monotone chain sorts lexicographically and builds lower and upper hulls;
- Graham scan and monotone chain run in \(O(n\log n)\) time;
- duplicate and collinear points require explicit output conventions;
- near-collinear configurations require numerical care;
- the hull supports later measurements, collision tests, spatial summaries, and geometric constructions.
The broader computational principle is that a complicated point cloud can often be simplified by identifying the small subset of extreme data that controls its outer geometry.
Where We Go Next
Convex hulls construct an outer boundary from a point set. The next lesson turns to a complementary problem: decomposing a region into simpler pieces.
Triangulation develops methods for dividing polygons, surfaces, and point sets into triangles, one of the most important structural operations in computational geometry.