Convex hull

The convex hull of a set is the smallest convex set containing it. In Euclidean space, it consists of all convex combinations of points in the set.

Convex combination: A weighted sum of points with nonnegative weights that sum to one. Every point in the hull is a convex combination of points from the original set.
Graham scan: An algorithm that computes the convex hull of planar points by sorting them around an extreme point. It builds a planar hull by discarding points that would make nonconvex turns.
Convex set: A set containing the line segment between every pair of its points. The hull is the smallest set with this defining property that contains the given points.
Concave hull: A boundary enclosing a point set that can preserve some of its inward indentations. Unlike the convex hull, it need not fill every indentation between the points.
Carathéodory's theorem: In d-dimensional space, every point in a set’s convex hull is a combination of at most d+1 points. It limits how many original points are needed to represent any hull point.
Quickhull: A divide-and-conquer algorithm for computing convex hulls in two or more dimensions. It recursively finds extreme points and partitions points outside candidate hull edges or facets.
Affine combination: A linear combination of points whose coefficients sum to one, without requiring nonnegative coefficients. Convex combinations are affine combinations with the additional constraint of nonnegative weights.
Alpha shape: A family of geometric shapes that captures the structure of a point set at a chosen scale. It can retain concavities and holes that a convex hull necessarily erases.
Supporting hyperplane: A hyperplane that meets a convex set while leaving the entire set in one closed half-space. Supporting hyperplanes characterize the hull’s boundary and separate outside points from it.
Chan's algorithm: An output-sensitive algorithm for computing the convex hull of planar points or points in fixed-dimensional space. Its running time depends on the number of hull vertices as well as the input size.

Linked from 22 pages