Convex Hull

TL;DR

The convex hull is the minimal convex boundary that encloses every point in a set.
It appears as the outermost closed loop of line segments connecting boundary points (visualizable as an inflated balloon around the points).
Common algorithms to compute it include Jarvis March (Gift Wrapping) and Quickhull.

Definition

The convex hull is the smallest convex shape that contains all of the points in the given set. It is the set of all points that are either on the boundary of the given set of points or are within the set.

Explanation

Geometric interpretation: the convex hull is the outermost boundary formed by a closed loop of line segments that connect points on the hull in a specific order.
Visual analogy: it can be visualized as the boundary of a balloon inflated around the set of points.
Convexity property: the convex hull is always a convex shape, meaning any line segment connecting two points on the hull lies completely within the hull.
Minimality property: it is the smallest convex set containing all points in the original set; accordingly, any point on the convex hull must be a vertex of the hull, and any point within the hull must be on the line segment connecting two vertices of the hull.
Geometric operations: quantities such as the area of the convex hull can be computed by subdividing the hull into triangles and summing their areas.

Examples

Jarvis March (Gift Wrapping)

Starts with an arbitrary point on the hull and iteratively adds the next hull point by finding the point that has the smallest angle relative to the previous point. The process repeats until the starting point is reached again, producing the convex hull.

Quickhull

Uses a divide-and-conquer approach: begin by dividing the set of points into two subsets using a line that passes through the points with the minimum and maximum x-coordinates. Compute the convex hulls of these subsets recursively, then merge the resulting hulls to form the overall convex hull.

Area calculation

The area of the convex hull can be calculated by dividing the hull into triangles and summing the areas of those triangles.

Use cases

Computer vision: object recognition via hulls of point sets.
Robotics: collision avoidance using hulls to represent object shape and size.
Machine learning: visualizing classifier decision boundaries by plotting convex hulls of different classes.

Notes or pitfalls

The convex hull is always convex: any line segment connecting two points on the hull lies entirely within the hull.
It is the smallest convex set that contains all points in the given set.
According to the source text, any point on the convex hull must be a vertex of the hull, and any point within the hull must lie on the line segment connecting two vertices of the hull.

Jarvis March (Gift Wrapping)
Quickhull
Convex set
Decision boundary
Classifier