Definition

Given a set of n points in d-dimensional space, a convex hull is the smallest convex set that contains all the points. It is a geometric concept that is often used in computer graphics, computational geometry, and optimization.

In mathematical terms, the convex hull of a set of points $$P = {p_1, p_2, \dots, p_n}$$ is the intersection of all convex sets that contain P, i.e.,

$$Convex Hull(P) = \bigcap { C \subseteq \mathbb{R}^d: C \text{ is convex and } P \subseteq C }$$

The convex hull is also known as the convex envelope of P. It is a closed, convex set that is uniquely determined by P.

Properties of Convex Hulls

The convex hull of a set of points has a number of useful properties, including:

• It is a convex set.
• It contains all of the original points.
• It is the smallest convex set that contains all of the original points.
• It is the intersection of all halfspaces that contain all of the original points.
• It is the union of all line segments that connect pairs of original points.
• It is a polyhedron if the original points are in general position.

Applications of Convex Hulls

Convex hulls are used in a variety of applications, including:

• Computational geometry: Convex hulls are used to solve a variety of geometric problems, such as finding the closest pair of points, the diameter of a set of points, and the volume of a convex polyhedron.
• Computer graphics: Convex hulls are used to create 3D models of objects.
• Optimization: Convex hulls are used to solve a variety of optimization problems, such as linear programming and quadratic programming.
• Robotics: Convex hulls are used to determine the workspace of a robot.

Algorithms for Computing Convex Hulls

There are a number of algorithms for computing convex hulls. The most common algorithms are:

• Graham's scan: Graham's scan is a simple and efficient algorithm that works in O(n log n) time.
• Jarvis's march: Jarvis's march is another simple and efficient algorithm that works in O(nh) time, where h is the number of points on the convex hull.
• Quickhull: Quickhull is a divide-and-conquer algorithm that works in O(n log n) time on average.
• Chan's algorithm: Chan's algorithm is a randomized algorithm that works in O(n log n) time with high probability.

Conclusion

Convex hulls are a fundamental concept in geometry with a wide range of applications. There are a number of algorithms for computing convex hulls, each with its own advantages and disadvantages.