CoreSource checked

Quickhull

Finds a convex hull by recursively choosing farthest outside points.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Intermediate
Family: Convex Hull
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready

Overview

Quickhull splits points by a line, picks the farthest point outside it, and recursively builds hull edges.

Core Concepts

geometric calculationgeometric predicatedivide and conquerconvex hullspatial relationshipcoordinate calculation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use Quickhull when you need to split points around candidate hull edges.
Use it for convex hull computation with inputs like set of points.
Use it when the problem depends on spatial relationships between points, lines, or shapes.
Use it when the Convex Hull tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when floating-point precision or degenerate cases are not handled.
Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not convex hull vertices.

What It Does

Splits points around candidate hull edges
Recursively keeps farthest outside points

Use Cases

Convex hull computation
Spatial preprocessing
Computational geometry demos

Inputs

Set of points

Outputs

Convex hull vertices

Key Formulas (1)

Point-line distance

distance = |cross(b − a, point − a)| / length(b − a)

distance = abs(cross(b - a, point - a)) / length(b - a)

Finds the farthest outside point from a candidate hull edge.

Pseudocode

1.Find extreme points to form a baseline
2.Split points on each side
3.Choose the farthest point from a line
4.Recurse on the two new line segments
5.Collect boundary points

Canonical Example

Input: points = [(0,0), (2,0), (1,1), (1,0)]
Output: spatial result such as a boundary, intersection, or containment answer
Explanation: Quickhull: The algorithm uses geometric tests to reason about the input shapes.

Implementation Notes

Keep the input contract explicit: Set of points.
Use this step as the implementation spine: Find extreme points to form a baseline.
Then preserve the next state change: Split points on each side.
Write tests for points on boundaries, equal coordinates, and very small distances.

Common Pitfalls

Quickhull is often fast in practice but has quadratic worst-case behavior.
Forgetting collinear, duplicate, overlapping, or boundary cases.
Returning convex hull vertices without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show farthest points forming new hull edges recursively.

Step 1 of 5: Find extreme points to form a baseline

recursive-hull

Notes

Quickhull operates in O(n log n) time and O(n) space within the Convex Hull family. Key governing relation: distance = abs(cross(b - a, point - a)) / length(b - a). Often compared with Convex Hull and Jarvis March.