The convex hull (or the hull), austerely beautiful object, is one of the most fundamental structure in computational geometry and plays a central role in pure mathematics. No wonder, the convex hull of a set of points is one of the most studied geometric problems both in algorithms and in pure mathematics. Indeed, computing convex hull is a fundamental operation in computational geometry. The in depth study of the hulls is useful in its own right and as a tool for constructing other structures in a variety of circumstances in the design of algorithms. The convex hull represents something of a success story in the area of algorithmic geometry. The computation of convex hull is one of the first papers in this area. There has been an amazing variety of research on hulls which ultimately leading to optimal algorithm known as Graham's scan. To trace the history of Graham's scan algorithm is worth it especially, in the context of algorithm design and analysis.
The importance of the topic demands an intuitive appreciation. So intuitively, if we think of each point in given set as being a nail sticking out from a board, the convex hull is the shape formed by a tight rubber band that surrounds all the nails.
In the computational geometry, the convex hull of Q is denoted by H(Q) or (as in CLRS) by CH(Q).
Preliminaries
Lets start with the algebraic point of view, which is quite useful both in mathematics and for computation. The algebraic viewpoint depends on the notion of convex combination. For instance, this viewpoint is used in finding the intersections between objects. In particular, determining whether any pair of segments intersects (see CLRS page 1021).
We say that the segment xy is the set of all points of the form α x + βy with α ≥ 0, β ≥ 0, and α + β = 1, where α and β are real numbers, while x and y are points or (equivalently) vectors. Now, a convex combination of points x1, ..., xk is a sum of the form α1x1 + α2x2 + ... + αkxk, where αi ≥ 0 for all i and α1 + ... + αk = 1. As a result, a line segment consists of all convex combinations of its endpoints, and a triangle consists of all convex combinations of its three corners. In three dimensions, a tetrahedron is the convex combinations of its four corners. Note that convex combinations (and affine combinations) lead to the concept of barycentric coordinates. ["Bary" means "heavy" in Greek.]
Definition of Convex Hull
The importance of the topic demands not only an intuitive appreciation (rubber band example above) but formal definition of a convex hull.
Definition 1 The convex hull Q is the set of all convex combinations of points in the given set Q.
Definition 2 The convex hull in d-dimensions is the set of all convex combinations of d + 1 (or fewer points) of points in the given set Q.
If we compare the Definition 1 and Definition 2, we'll see that in Definition 2 only d + 1 points are needed. As a result, the hull of a 2-dimensional set is the convex combinations of its subsets of three points (see preliminaries), each determine a triangle. That the (d + 1)-points definition is equivalent to the all-points definition (i.e., Definition 1) is known as Caratheodory's Theorem.
Definition 3 The convex hull of a set points Q is the intersection of all convex sets that contains Q.
The Definition 3 is much clearer than the Definition 1 and Definition 2 because it does depend on the notion of convex combination. But, the problem with Definition 3 is that the notion of "all convex sets" is not easy to grasp.
Definition 4 The convex hull of a set of points Q is the intersection of all halfspaces that contain Q.
This is perhaps the clearest definition, equivalent to all the previous ones. But, the problem with Definition 4 is that the "equivalence" is not trivial.
Definition 5 The convex hull of a finite set of points Q in the plane is the smallest convex polygon P that encloses Q. Here, the notion of "smallest" is in the sense that there is no other polygon P' such that (P is a superset of P' is a superset or equal to Q).
The Definition 5 certainly not suggesting any easy algorithm.
Definition 6 The convex hull of a finite set of points Q in the plane is the enclosing convex polygon P with smallest area.
The Definition 6 is quite intuitive especially when we use the notion of "smallest" as in definition 5. But, the problem here is that this definition is not mathematically obvious. And, certainly not suggesting any easy algorithm.
Definition 7 The convex hull of a finite set of points Q in the plane is the enclosing convex polygon P with smallest perimeter.
Again, like Definition 6, it is intuitive with the notion of "smallest" and like Definition 6, an easy algorithm is not obvious.
Definition 8 The convex hull of a set of points Q in the plane is the union of all the triangles determined by points in Q.
The Definition 8 is just a restatement of Definition 2. But this form of the definition hints at a method of computation.
Definition 9 (CLRS) The convex hull of a set Q of points is the smallest convex polygon P for which each point in set Q is ether on the boundary of P or in its interior.
That is, the convex hull is the smallest convex polygon containing the points:
Polygon: A region of the plane bounded by a cycle of line segments, called edges, joined end-to-end in a cycle. Points where two successive edges meet are called vertices.
Convex: For any two points p, q inside the polygon, the line segment pq is completely inside the polygon. Formally, a set S is convex if p is in S and q is in S implies that the segment pq is a subset of S. See the figure below. Note that this can be taken as the primary definition of convexity.
Smallest: Any convex proper subset of the convex hull excludes at least one point in P. This implies that every vertex of the convex hull is a point in P.
Equivalently, we can also define the convex hull as the largest convex polygon whose vertices are all points in P, or the unique convex polygon that contains P and whose vertices are all points in P. Notice that P might have interior points that are not vertices of the convex hull.
Definition 10 Mathematically speaking, we say the convex envelop for set of point Q in a real vector space V is the minimal convex set containing Q. In the mathematics literature, the convex hull of Q is denoted by conv Q.
In mathematics, envelop is a curve (surface) that is tangential to each one of a family of curves (surface) in a plane (3-dimensions). Recall (from your linear algebra Class), a vector space is a mathematical structure formed by a collection of vectors.
Applications of Convex Hull
The computation of the convex hull of a finite set of points has found applications in diverse areas, such as pattern recognition, image processing, robotics, and stock cutting and allocation. There are numerous applications in the literature. Lets briefly look at a few of them.
Collision avoidance: Suppose our problem is to plan the path for a robot from point a to point b in the presence of obstacles. If the convex hull of a robot avoids collision with obstacles, then so does the robot. So, the convex hull structure often used to plan paths.
Fitting ranges with a line: Suppose our problem is to find a straight line that fits between a collection of data ranges. Our solution requires finding a straight line that fits between a collection of data ranges maps to finding the convex region common to a collection of halfplanes.
Smallest box: Suppose our problem is to place an object (convex polygon) in a smallest box. The smallest area rectangle that encloses a polygon has at least one side flush with the convex hull of the polygon, and so hull is computed at the first step of minimum rectangle algorithms. Similarly, finding the smallest three-dimensional box surrounding an object in space depends on the convex hull of the object.
Shape analysis: Shapes may be classified for the purpose of matching by their "convex deficiency trees," structures that depend for their computation on convex hulls.
Problem
So, the problem we want to solve is this: Given a set Q = {p1, p2, ..., pn} of points in the plane, compute a list that contains those points from Q that are the vertices of CH(Q), listed in counterclockwise order.
Input = Set of points: p1, p2, p3, p4, p5, p6, p7, p8, p9
Output = Representation of the convex hull: p8, p5, p4, p9, p2
Let me repeat the problem! Given n points on the plane, our problem is to find their convex hull. This problem is as fundamental to computational geometry as sorting to general algorithms. This problem also cultivates the ground for the solution of a number of seemingly unrelated problems in computational geometry.
Lower Bound on Convex Hull
In order to established the lower bound for the problem of computing convex hull of the set of n points in the plane, we reduce sorting problem into convex hull problem in the sense that convex hull algorithm can be used to solve sorting problem with little additional work. In other words, if we solve hull problem quickly, we can solve sorting problem quickly.
Suppose, we have an unsorted list of numbers to be sorted, x1, x2, …, xn, where xi ≥ 0 for all i. Also, suppose we have an algorithm HULL that constructs the convex hull of n points in T(n) time. Our task is to use HULL to solve SORTING in time T(n) + O(n) where the O(n) represents additional time to convert the solution of HULL problem to the solution of SORTING problem.
Form the set of two-dimensional points (xi, xi2). These points lie on the parabola y = x2. Run algorithm HULL to construct the hull. Clearly, every point is on the hull. Identify the lowest point a on the hull in O(n) time; this corresponds to the smallest xi. The order in which the points occur on the hull counterclockwise from ‘a’ is their sorted order. Thus, we can use HULL algorithm to sort.
What we have shown that if we had a fast algorithm for the HULL, we could sort faster than O(n log n); but this is known to be impossible. This implies that the lower bound of convex hull is same as that of sorting and that is Ω(n log n).
Updated: May 5, 2010.