✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-231

Convex Hull Algorithms

Convex Hull Algorithms find the smallest convex polygon that contains a given set of points. The convex hull is often described as the shape formed by stretching a tight rubber band around all the points.

Explanation

Overview

The convex hull of a set of points is the smallest convex set containing every point in that collection. In two-dimensional computational geometry, it is usually represented as a polygon whose vertices are selected from the input points. Points inside the hull are not required to appear as hull vertices.

How it works

Collect all input points.; Sort or select an initial extreme point, depending on the chosen algorithm.; Use orientation tests to determine whether candidate points belong on the outer boundary.; Remove points that would create an inward or incorrect turn.; Continue until the complete outer boundary is constructed.; Return the hull vertices in a consistent order.

Key concepts

Convex sets; Hull boundary; Extreme points; Orientation test; Cross product; Counterclockwise traversal

Time complexity

algorithm: Graham Scan; complexity: O(n log n); algorithm: Monotonic Chain; complexity: O(n log n); algorithm: Jarvis March; complexity: O(nh), where h is the number of hull vertices

Space complexity

O(n) for common implementations that store sorted points and the hull boundary.

Example

points: 0; 0; 2; 0; description: The points form a collection containing several boundary and interior points. The convex hull surrounds the entire collection while excluding interior points from its vertex list.; hullVertices: 0; 0; 4; 0

Applications

Computer graphics; Geographic data analysis; Collision detection; Pattern recognition; Robotics; Shape analysis

Example or application

Points

    • 0

    • 0

    • 2

    • 0

    • 4

    • 0

    • 4

    • 3

    • 2

    • 1

    • 0

    • 3

    • 2

    • 2

Description

The points form a collection containing several boundary and interior points. The convex hull surrounds the entire collection while excluding interior points from its vertex list.

Hull Vertices

    • 0

    • 0

    • 4

    • 0

    • 4

    • 3

    • 0

    • 3

Definition

The convex hull of a set of points is the smallest convex set containing every point in that collection. In two-dimensional computational geometry, it is usually represented as a polygon whose vertices are selected from the input points. Points inside the hull are not required to appear as hull vertices.

Geometric Properties

  • The convex hull contains every input point.

  • The hull boundary forms a convex polygon.

  • Every line segment connecting two points inside the hull remains inside the hull.

  • The extreme input points form the vertices of the hull.

  • Points inside the hull do not change its outer boundary.

Major Algorithms

NameDescriptionTime ComplexityMain Idea

Graham Scan

Sorts points around a reference point and uses a stack to remove points that would create an incorrect turn.

O(n log n)

Process points in angular order while maintaining a counterclockwise boundary.

Monotonic Chain

Sorts points lexicographically and constructs lower and upper hulls using orientation tests.

O(n log n)

Build two boundary chains and combine them to form the complete convex hull.

Jarvis March

Starts from an extreme point and repeatedly selects the next boundary point using orientation tests.

O(nh), where h is the number of hull vertices

Wrap around the point set by selecting one outer boundary point at a time.

How It Works

  • Collect all input points.

  • Sort or select an initial extreme point, depending on the chosen algorithm.

  • Use orientation tests to determine whether candidate points belong on the outer boundary.

  • Remove points that would create an inward or incorrect turn.

  • Continue until the complete outer boundary is constructed.

  • Return the hull vertices in a consistent order.

Orientation Test

Description

The orientation test uses the sign of a cross product to determine the direction of a turn formed by three points.

Formula

cross = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)

Interpretation

  • Positive: counterclockwise turn.

  • Negative: clockwise turn.

  • Zero: collinear points.

Implementation

Algorithm

Monotonic Chain

Pseudocode

  • function cross(O, A, B):

  • return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)

  • function convexHull(points):

  • sort points by x-coordinate, then y-coordinate

  • remove duplicate points

  • lower = empty list

  • for point in points:

  • while length(lower) >= 2 and cross(lower[-2], lower[-1], point) <= 0:

  • remove last element from lower

  • append point to lower

  • upper = empty list

  • for point in reverse(points):

  • while length(upper) >= 2 and cross(upper[-2], upper[-1], point) <= 0:

  • remove last element from upper

  • append point to upper

  • remove last point from lower

  • remove last point from upper

  • return lower + upper

Note

The comparison used in the orientation condition determines how collinear boundary points are handled. If all boundary points must be retained, the algorithm needs a different collinearity policy.

Time Complexity

AlgorithmComplexity

Graham Scan

O(n log n)

Monotonic Chain

O(n log n)

Jarvis March

O(nh), where h is the number of hull vertices

Space Complexity

O(n) for common implementations that store sorted points and the hull boundary.

Key Concepts

  • Convex sets

  • Hull boundary

  • Extreme points

  • Orientation test

  • Cross product

  • Counterclockwise traversal

  • Geometric sorting

  • Collinear points

Advantages

  • Identifies the outer boundary of a point collection.

  • Provides an efficient foundation for many geometric computations.

  • Supports spatial analysis and collision-related applications.

  • Offers multiple algorithms suitable for different input distributions.

Limitations

  • Duplicate and collinear points require explicit handling.

  • Floating-point coordinates can introduce precision problems.

  • Different algorithms have different performance characteristics.

  • The correct hull representation depends on whether collinear boundary points should be retained.

Applications

  • Computer graphics

  • Geographic data analysis

  • Collision detection

  • Pattern recognition

  • Robotics

  • Shape analysis

  • Spatial clustering

  • Computational geometry

Related Topics

  • Computational Geometry Fundamentals

  • Sweep Line Algorithms

  • Sorting Algorithms

  • Cross Product

  • Polygon Algorithms

Practice Questions

QuestionAnswer

What is a convex hull?

The smallest convex shape containing every point in a given point set.

What is the common time complexity of Graham Scan?

O(n log n).

What does the orientation test determine?

Whether three points make a clockwise turn, counterclockwise turn, or are collinear.

What does h represent in the Jarvis March complexity?

The number of points on the convex hull boundary.

Learning Objectives

  • Explain the central idea and purpose of convex hull algorithms.

  • Identify the assumptions, inputs, and conditions relevant to convex hull algorithms.

  • Evaluate an application of convex hull algorithms for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Specialized Algorithms and Computational Topics

Suggest a correction or source · More in Algorithms & Data Structures