Computational Geometry,Fundamental Structures:Convex Hulls

Convex Hulls

A set A ⊂ Rd is convex if for any two points p, q ∈ A the segment pq is completely contained in A. The convex hull of a set S of objects is the smallest convex set that contains all objects in S, that is, the most tightly fitting convex bounding volume for S. For example, if S is a set of objects in the plane, we can obtain the convex hull by taking a large rubber band around the objects and then releasing the band; the band will snap around the objects and the resulting shape is the convex hull. More formally, we can define CH(S) as the intersection of all convex sets containing all objects in S:

We denote the convex hull of the objects in S by CH(S).

It is easy to see that the convex hull of a set of line segments in the plane is the same as the convex hull of the endpoints of the segments. More generally, the convex hull of a set of bounded polygonal objects in Rd is the same as the convex hull of the vertices of the objects. Therefore we will restrict our discussion to convex hulls of sets of points. Table 62.2 gives an overview of the results on the complexity and construction of convex hulls discussed below.

Complexity

Let P be a set of n points in Rd. The convex hull of P , denoted by CH(P ), is a convex polytope whose vertices are a subset of the points in P . The complexity of a polytope is defined as the total number of k-facets† (that is, k-dimensional features) on the boundary of the polytope, for k = 0, 1,... ,d − 1: the complexity of a planar polygon is the total number of vertices and edges, the complexity of a 3-dimensional polytope is the total number of vertices, edges, and faces, and so on.

Because the vertices of CH(P ) are a subset of the points in P , the number of vertices of CH(P ) is at most n. In the plane this means that the total complexity of the convex hull is O(n), because the number of edges of a planar polygon is equal to the number of vertices. In higher dimensions this is no longer true: the number of k-facets (k > 0) of a polytope can be larger than the number of vertices. How large can this number be in the worst case? In R3, the total complexity is still O(n). This follows from Euler’s formula, which states that for a convex polytope in R3 with V vertices, E edges, and F faces it holds that V − E + F = 2. In higher dimensions, the complexity can be significantly higher: the worst-case complexity of a convex polytope with n vertices in Rd is Θ(nLd/2J).

In fact, the bound on the complexity of the convex hull immediately follows from the results of the previous section if we apply duality. To see this, consider a set P of n points in the plane. For simplicity, let us suppose that CH(P ) does not have any vertical edges and that no three points in P are collinear. Define the upper hull of P , denoted by UH(P ), as the set of edges of CH(P ) that bound CH(P ) from above. Let P ∗ be the set of lines that are the duals of the points in P . A pair p, q ∈ P defines an edge of UH(P ) if and only if all other points r ∈ P lie below the line through p and q. In the dual this means that all lines r∗ ∈ P ∗ lie above the intersection point p∗ ∩ q∗. In other words, p∗ ∩ q∗ is a vertex on the lower envelope LE (P ∗) of the lines in P ∗. Furthermore, a point p ∈ P is a vertex of UH(P ) if and only if its dual p∗ defines an edge of LE (P ∗). Thus there is a one-to-one correspondence between the vertices (or, edges) of UH(P ), and the edges (or, vertices) of LE (P ∗). In higher dimensions a similar statement is true: there is a one-to-one correspondence between the k-facets of the upper hull of P and the (d − k − 1)-facets of the lower envelope of P ∗. The bound on the complexity of the convex hull of a set of n points in Rd therefore follows from the Θ(nLd/2J) bound on the complexity of the lower envelope of a set of n hyperplanes Rd.

The Θ(nLd/2J) bound implies that the complexity of the convex hull can be quite high when the dimension gets large. Fortunately this is not the case if the points in P are distributed uniformly: in that case only few of the points in P are expected to show up as a vertex on the convex hull. More precisely, the expected complexity of the convex hull of a set P that is uniformly distributed in the unit hypercube is O(logd−1 n) [18, 19].

Construction

We now turn our attention to algorithms for computing the convex hull of a set P of n points in Rd. In the previous subsection we have shown that there is a correspondence between the upper hull of P and the lower envelope of P ∗, where P ∗ is the set of hyperplanes dual to the points in P . It follows that any algorithm that can compute the convex hull of a set

of points in Rd can also be used to compute the intersection of a set of half-spaces in Rd, and vice versa.

First consider the planar case. By a reduction from sorting, one can show that Ω(n log n) is a lower bound on the worst-case running time of any convex-hull algorithm. There are many different algorithms that achieve O(n log n) running time and are thus optimal in the worst case. One of the best known algorithms is called Graham’s scan [7, 26]. It treats the points from left to right, and maintains the upper hull of all the points encountered so far. To handle a point pi, it is first added to the end of the current upper hull. The next step is to delete the points that should no longer be part of the hull. They always form a consecutive portion at the right end of the old hull, and can be identified easily—see Fig. 62.5.

After these points have been deleted, the next point is handled. Graham’s scan runs in linear time, after the points have been sorted from left to right. This is optimal in the worst case.

The Ω(n log n) lower bound does not hold if only few points show up on the convex hull. Indeed, in this case it is possible to do better: Kirkpatrick and Seidel [34], and later Chan [10], gave output-sensitive algorithms that compute the convex hull in O(n log k) time, where k is the number of vertices of the hull.

In R3, the worst-case complexity of the convex hull is still linear, and it can be computed in O(n log n) time, either by a deterministic divide-and-conquer algorithm [43] or by a simpler randomized algorithm [17, 39, 51]. In dimensions d> 3, the convex hull can be computed in Θ(nld/2J) time [14]. This is the same as the worst-case complexity of the hull, and therefore optimal. Again, the simplest algorithms that achieve this bound are randomized [17, 39, 51].

There is also an output-sensitive algorithm by Chan [10], which computes the convex hull in O(n log k + (nk)1−1/(ld/2J+1) logO(1) n) time, where k is its complexity.

As remarked earlier, the expected complexity of the convex hull of a set of n uniformly distributed points is much smaller than the worst-case complexity. This means that if we use an output-sensitive algorithm to compute the convex hull, its expected running time will be better than its worst-case running time. One can do even better, however, by using specialized algorithms. For example, Dwyer [18] has shown that the convex hull of points distributed uniformly in e.g. the unit hypercube can be computed in linear expected time.

Dynamic Convex Hulls

In some applications the set P changes over time: new points are inserted into P , and some existing points are deleted. The convex hull can change drastically after an update: the insertion of a single point can cause Θ(n) points to disappear from the convex hull, and the deletion of a single point can cause Θ(n) points to appear on the convex hull. Surprisingly, it is nevertheless possible to store the convex hull of a planar point set in such a way that any update can be processed in O(log2 n) in the worst case, as shown by Overmars and van Leeuwen [47]. The key to their result is to not only store the convex hull of the whole set, but also information about the convex hull of certain subsets. The structure of Overmars and van Leeuwen roughly works as follows. Suppose we wish to maintain UH(P ), the upper hull of P ; maintenance of the lower hull can be done similarly. The structure to maintain UH(P ) is a balanced binary tree T , whose leaves store the points from P sorted by x- coordinate. The idea is that each internal node ν stores the upper hull of all the points in the subtree rooted at ν. Instead of storing the complete upper hull at each node ν, however, we only store those parts that are not already on the upper hull of nodes higher up in the tree. In other words, the point corresponding to a leaf µ is stored at the highest ancestor of µ where it is on the upper hull—see Fig. 62.6 for an illustration.

Note that the root still stores the upper hull of the entire set P . Because a point is stored in only one upper hull, the structure uses O(n) storage. Overmars and van Leeuwen show how to update the structure in O(log2 n) time in the worst case.

Although the result by Overmars and van Leeuwen is more than 20 years old by now, it still has not been improved in its full generality. Nevertheless, there have been several advances in special cases. For example, for the semi-dynamic case (only insertions, or only deletions), there are structures with O(log n) update time [30, 42]. Furthermore, O(log n) update time can be achieved in the off-line setting, where the sequence of insertions and deletions is known in advance [32]. Improvements are also possible if one does not need to maintain the convex hull explicitly. For example, in some applications the reason for maintaining the convex hull is to be able to find the point that is extreme in a query direction, or the intersection of the convex hull with a query line. Such queries can be answered in logarithmic time if the convex hull vertices are stored in order in a balanced binary tree, but it is not necessary to know all the convex hull vertices explicitly to answer such queries.

This observation was used by Chan [11], who described a fully dynamic structure that can answer such queries in O(log n) time and that can be updated in O(log1+ε n) time. This result was recently improved by Brodal and Jacob [9], who announced a structure that uses O(n) storage, has O(log n) update time, and can answer queries in O(log n) time. Neither Chan’s structure nor the structure of Brodal and Jakob, however, can report the convex hull in time linear in its complexity, and the update times are amortized.