Chapter 2
Two- and Three-Dimensional Convex Hulls
In this chapter, we present two 0(n log /i)-time convex hull algorithms in the plane P2, the second of which is also extended to E3 with the same optimal time complexity. Although algorithms with this time complexity were known, our methods are simpler than the previous and also illustrate the basic ideas to be used in the rest of this thesis for constructing convex hulls in higher dimensions. In particular, the first planar convex hull algorithm we present, which can be considered as a simplification of the original optimal method of Kirkpatrick and Seidel [KS86], serves as the basis of the four-dimensional output-sensitive algorithm in the next chapter.
2.1    A Simplified "Ultimate Planar Convex Hull Algorithm"
This section describes a simple O(nlog h) convex hull algorithm in the plane. Since our algorithm can be viewed as a simplification of Kirkpatrick and Seidel's planar convex hull algorithm, we first sketch here their method for comparison.
Given an n-point set P C we want to construct the convex hull of P. It suffices to compute just the upper hull of P, consisting of the sequence of hull edges that have an upward normal vector. Then the lower hull can be computed in a similar manner by reflection and the convex hull can be obtained by joining these two hulls.
Kirkpatrick and Seidel's algorithm constructs the upper hull of P as follows: (i) find a point p* G P with the median x-coordinate, (ii) compute the edge p~ip~2 of the upper hull
14
Chapter 2.   Two- and Three-Dimensional Convex Hulls
15
that intersects the vertical line through p* (x[pi] < x[p*] < x[p2])} and (iii) recursively compute the upper hull of all points left of (and including) p\ and the upper hull of all points right of (and including) p2.
To find the edge p\Pi (the bridge) that intersects a given vertical line in step (ii), Kirkpatrick and Seidel used a prune-and-search procedure, similar to the prune-and-search linear programming algorithm of Dyer [Dye84] and Megiddo [Meg83b, Meg84]. (In fact, bridge-finding can be formulated as a linear program in dual space.) Here is a high-level description what is involved in this prune-and-search procedure: First, points are paired, the slope of the line through each pair is calculated, and the median slope m is computed. Then the upper-hull vertex pm with a supporting line of slope m is found. A comparison involving pm and the given vertical line is then performed, which allows one point in half of the pairs be pruned. This step eliminates 1/4 of the points and the procedure is repeated.
This ends our brief sketch of Kirkpatrick and Seidel's algorithm. As a summary, we can say that their algorithm has two levels: the lower level is a prune-and-search procedure, and on top of that is a divide-and-conquer method. Our main observation is that we can get a simpler algorithm if we combine these two levels into one, i.e., if we use pruning directly for divide-and-conquer rather than for searching. As a result, we can skip the step that computes the point p* with median x-coordinate and avoid actually searching for the bridge at each recursive step.
2.1.1    The prune-and-divide algorithm in the plane
We now give the details of our simplified planar convex hull algorithm. As in Kirkpatrick and Seidel's algorithm, only the upper hull of the given n-point set P C E2 is computed. We first pair the points of P arbitrarily and calculate the slope of the line through each pair. We then find the median slope m and compute the upper-hull vertex pm that has a
Chapter 2.   Two- and Three-Dimensional Convex Hulls
16
Figure 2.2: Pairing and pruning points in the plane. Points marked L belong to P^, points marked R belong to Pr, and points marked X belong to neither sets.
supporting line of slope m; this vertex can be computed by taking the maximum along a projection of P parallel to m. The x-coordinate of pm is then used to divide P into two parts: P^, which contains pm and all points to its left, and Pr, which contains pm and all points to its right.
Now, if a pair has slope less than m, then the right point in the pair cannot participate in the upper hull of Pi and thus can be pruned from Pi. Similarly, if a pair has slope greater than m, then its left point in the pair cannot participate in the upper hull of Pr and can be pruned from Pr. Since half (n/4) of the pairs have slope less than the median m and half have slope greater than m, pruning ensures that Pi and Pr each contain at most 3n/4 points. We then recursively compute the upper hull of Pi and Pr. See Figure 2.2 for an example.
Chapter 2.   Two- and Three-Dimensional Convex Hulls
17
The pseudocode of the algorithm is given below. For convenience, we assume that the leftmost and rightmost points pi and pr of P have been identified and we let n be the cardinality of the set P* = P — {pi7pr} instead. In the interest of practical efficiency, line 1 has been added to the algorithm; it does not affect asymptotic worst-case performance.
Algorithm DivideHull2d(P*,^,pr)
[ Given n-point set P' C E2 and points pe,pr G E2 such that x[pi] < x[p] < x[pr] for all p £ F', return the sequence of edges of the upper hull of P = P' U {pi7pr}. ]
1. discard points from P' that lie below pipr
2. if P' = 0 then return {pepr}
if P' = {p} then return (pep, ppr)
3. arbitrarily choose |_n/2j disjoint pairs {{si, ti},{s|n/2j, t\n/2\}} from P'
and order each pair so that x[si] < x[ti]
4. let mi = (y[ti\ - y[s8]) / (x[ti\ - x[si\), i = 1,. . . , [n/2\
and m = median of (mi,. . ., m[ri/2j)
5. let pm = point in P that maximizes y[pm] — m ■ x[pm]
6. let P' = {p G P' : x[p] < x[pm]} —      : m8- < m}
P* = {p G P* : x[p] > x[pm]} - {si : m8 > m}
7. if pm = pr then return DivideHull2d(P/,^,pr) if Pm = W then return DivideHull2d(Pr*, pi} pr) otherwise return the concatenation of
DivideHull2d(P/,^,pm) and DivideHull2d(Pr*,pm}pr)
Remark: It is not difficult to modify DivideHull2d() to work for point sets P not in general position. When there are more than one point in P that maximize y[pm] — m-x[pm] in line 5, we simply pick the leftmost one. When two points in a pair share the same x-coordinate, we can eliminate the bottom one.
Chapter 2.   Two- and Three-Dimensional Convex Hulls
18
T(n,h) < <
2.1.2   Analysis of the prune-and-divide algorithm in the plane
Let T(n, h) be the running time of algorithm DivideHull2d() on a point set with n + 2
points (i.e., n points excluding pi and pr) and h + 1 upper-hull vertices (i.e., h upper-hull
edges). By noting that median-finding (line 4) can be done in linear time, we obtain the
following recurrence for T(n,/i), where c denotes a constant:
c if n < 1
T(ri£} h) + cn if n > 2 and hr = 0
T(nr, h) -\- cn if n > 2 and hi = 0
T(ri£} hi) + T(nr, /ir) + cn if n > 2 and     hr > 1
for some 0 < n^, nr < [3n/4] and hi, hr > 0 with     + nr < n and hi -\- hr = h.
Using the concavity of the logarithm, one can then prove that T(n, h) = 0(n log h) by induction. Here, we observe an alternative proof that is perhaps simpler as it avoids the use of induction. The proof is more general and provides better insight into recurrences of this kind by examining their recursion trees.
Let T be a rooted tree in which each node v is assigned a cost c(u) £ [0, oo). We say that the cost function c is a-fading for a constant a £ (0,1) if c(/i) < a c(u) for every node ji and its parent v. As part of the analysis of their 3-d output-sensitive convex hull algorithm, Edelsbrunner and Shi [ES91, Lemma 3.1] proved that the total cost in such a tree is asymptotically bounded by the per-level cost times the logarithm of the number of nodes. Their proof uses a path compression operation that transforms T into a balanced tree. We give a simple, short proof of their result that avoids path compression altogether; we then improve the bound to depend on the number of leaves rather than the number of nodes.
Lemma 2.1.1 In a recursion tree T with m nodes and £ leaves and an a-fading cost function c, if the sum of the costs at each level is bounded by C, then the sum of the costs of all nodes in T is (i) at most C(log^ m + 2) and (ii) at most C(log^ £+1 + 1/(1 — a)).
Chapter 2.   Two- and Three-Dimensional Convex Hulls
19
Proof: Number the levels of the tree 0, 1, 2, ...with the root at level zero. Let k = |^log1^Q,mJ. The sum of the costs at levels 0,1,..., A; is bounded by C(k + 1) < C(l °Si/a ra + 1). Furthermore, by the a-fading property, each node on a level greater than k has cost bounded by Cak+1 < C/ra; hence, the sum of the costs at level k + 1, k + 2,. . . is bounded by C. Part (i) follows.
To prove part (ii), we choose k = [log^^J instead. As before, the sum of the costs at levels 0,1,. . . , k is bounded by C(k + 1) < C{\oglja£ + 1). Thus, we just have to account for the costs of nodes at levels greater than k. Note that each node belongs to some root-to-leaf path in T. By the a-fading property, the sum of the costs at levels k + 1, k + 2,. . . along such a path is bounded by
Cak+1 + Cak+2 + . . . = ^— < L
I-a   ~ (l-a)£
Since there are £ root-to-leaf paths in total, the sum of the costs at levels k + 1, k + 2,. . . is bounded by C/(l — a). Part (ii) follows. □
With Lemma 2.1.1, it is now easy to show that the running time of algorithm DivideHull2d() is O(nlog h). Consider the recursion tree generated by the calls to DivideHull2d(). It is clear that the sum of the costs at each level of the tree is bounded by cn and that the cost function satisfies the (3/4)-fading property. Since the number of leaves is at most h (as a new edge is discovered at every leaf), Lemma 2.1.1 (ii) immediately implies that the total cost of the algorithm is bounded by cn log4/3 h + 0{n).
The storage requirement of the algorithm is clearly linear. We have thus shown:
Theorem 2.1.2 Algorithm DivideHull2d() computes the (h + 1)-vertex upper hull of an (n + 2)-point set P C E2 in O(nlogh) time and 0{n) space.
Remarks:
1. Compared to the algorithm by Kirkpatrick and Seidel, DivideHull2d() is faster