Convex Hull

The convex hull of a set of points in the plane is the smallest convex polygon such that every point in the set lies on the boundary or in the interior of the polygon. Intuitively, if the points were nails driven into a board, the convex hull would be the shape formed by wrapping a taut rubber band around all the nails. Every vertex of the convex hull is a point from the original set, and the polygon has no inward-facing angles.

Several efficient algorithms compute the convex hull. Graham scan sorts points by polar angle and processes them in order, achieving O(n log n) time. Jarvis march (gift wrapping) iteratively selects the next hull vertex, running in O(nh) time where h is the number of hull vertices. Divide-and-conquer algorithms split the point set, compute sub-hulls, and merge them. The quickhull algorithm partitions points relative to extreme edges and recursively processes subsets. Most GISGISGeographic Information Systems (GIS) enable users to analyze and visualize spatial data to uncover patterns, relation... software provides built-in convex hull tools that implement these algorithms transparently.

Ecologists compute convex hulls to estimate the home range or geographic extent of a species based on observation points. Conservation biologists use minimum convex polygons as a standard method for reporting species range. Logistics analysts define the bounding area of a delivery fleet or customer base. Urban planners compute the spatial footprint of facility networks. In computational geometry, convex hulls serve as a preprocessing step for more complex operations including Delaunay triangulationDelaunay TriangulationDelaunay triangulation connects a set of points into a network of non-overlapping triangles such that no point lies i... and collision detection.

Convex hulls can overestimate the true extent of a point set because they cannot represent concavities. A widely spread cluster with a concave distribution will be enclosed by a convex polygon that includes large empty areas. For tighter boundary estimation, concave hullConcave HullA concave hull is a tightly fitting boundary around a set of points that follows the shape of the point distribution,... algorithms are preferred.