Home | | Design and Analysis of Algorithms | Convex Hull Problems by Divide and Conquer

# Convex Hull Problems by Divide and Conquer

find the smallest convex polygon that contains n given points in the plane. We consider here a divide-and-conquer algorithm called quickhull because of its resemblance to quicksort.

The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer

In Section 3.3, we discussed the brute-force approach to solving two classic prob-lems of computational geometry: the closest-pair problem and the convex-hull problem. We saw that the two-dimensional versions of these problems can be solved by brute-force algorithms in  (n2) and O(n3) time, respectively. In this section, we discuss more sophisticated and asymptotically more efficient algorithms for these problems, which are based on the divide-and-conquer technique.

Convex-Hull Problems

Let us revisit the convex-hull problem, introduced in Section 3.3: find the smallest convex polygon that contains n given points in the plane. We consider here a divide-and-conquer algorithm called quickhull because of its resemblance to quicksort.

Let S be a set of n > 1 points p1(x1, y1), . . . , pn(xn, yn) in the Cartesian plane. We assume that the points are sorted in nondecreasing order of their x coordinates, with ties resolved by increasing order of the y coordinates of the points involved. It is not difficult to prove the geometrically obvious fact that the leftmost point p1 and the rightmost point pn are two distinct extreme points of the setŌĆÖs convex The boundary of the convex hull of S is made up of two polygonal chains: an ŌĆ£upperŌĆØ boundary and a ŌĆ£lowerŌĆØ boundary. The ŌĆ£upperŌĆØ boundary, called the upper hull, is a sequence of line segments with vertices at p1, some of the points in S1 (if S1 is not empty) and pn. The ŌĆ£lowerŌĆØ boundary, called the lower hull, is a sequence of line segments with vertices at p1, some of the points in S2 (if S2 is not empty) and pn. The fact that the convex hull of the entire set S is composed of the upper and lower hulls, which can be constructed independently and in a similar fashion, is a very useful observation exploited by several algorithms for this problem.

For concreteness, let us discuss how quickhull proceeds to construct the upper hull; the lower hull can be constructed in the same manner. If S1 is empty, the upper hull is simply the line segment with the endpoints at p1 and pn. If S1 is not empty, the algorithm identifies point pmax in S1, which is the farthest from the line Therefore, the algorithm can continue constructing the upper hulls of p1 Ōł¬ S1,1 Ōł¬ pmax and pmax Ōł¬ S1,2 Ōł¬ pn recursively and then simply concatenate them to get the upper hull of the entire set p1 Ōł¬ S1 Ōł¬ pn.

Now we have to figure out how the algorithmŌĆÖs geometric operations can be actually implemented. Fortunately, we can take advantage of the following very useful fact from analytical geometry: if q1(x1, y1), q2(x2, y2), and q3(x3, y3) are three arbitrary points in the Cartesian plane, then the area of the triangle q1q2q3 is equal to one-half of the magnitude of the determinant while the sign of this expression is positive if and only if the point q3 = (x3, y3) is to

ŌłÆŌłÆŌłÆŌåÆ

the left of the line q1 q2 . Using this formula, we can check in constant time whether a point lies to the left of the line determined by two other points as well as find the distance from the point to the line.

Quickhull has the same  (n2) worst-case efficiency as quicksort (Problem 9 in this sectionŌĆÖs exercises). In the average case, however, we should expect a much better performance. First, the algorithm should benefit from the quicksort-like savings from the on-average balanced split of the problem into two smaller subproblems. Second, a significant fraction of the pointsŌĆönamely, those inside p1pmaxpn (see Figure 5.9)ŌĆöare eliminated from further processing. Under a natural assumption that points given are chosen randomly from a uniform dis-tribution over some convex region (e.g., a circle or a rectangle), the average-case efficiency of quickhull turns out to be linear [Ove80].

Exercises 5.5

a. For the one-dimensional version of the closest-pair problem, i.e., for the problem of finding two closest numbers among a given set of n real num-bers, design an algorithm that is directly based on the divide-and-conquer technique and determine its efficiency class.

b. Is it a good algorithm for this problem?

Prove that the divide-and-conquer algorithm for the closest-pair problem examines, for every point p in the vertical strip (see Figures 5.7a and 5.7b), no more than seven other points that can be closer to p than dmin, the minimum distance between two points encountered by the algorithm up to that point.

Consider the version of the divide-and-conquer two-dimensional closest-pair algorithm in which, instead of presorting input set P , we simply sort each of the two sets Pl and Pr in nondecreasing order of their y coordinates on each recursive call. Assuming that sorting is done by mergesort, set up a recurrence relation for the running time in the worst case and solve it for n = 2k.

Implement the divide-and-conquer closest-pair algorithm, outlined in this section, in the language of your choice.

Find on the Web a visualization of an algorithm for the closest-pair problem. What algorithm does this visualization represent?

The Voronoi polygon for a point p of a set S of points in the plane is defined to be the perimeter of the set of all points in the plane closer to p than to any other point in S. The union of all the Voronoi polygons of the points in S is called the Voronoi diagram of S.

What is the Voronoi diagram for a set of three points?

Find a visualization of an algorithm for generating the Voronoi diagram on the Web and study a few examples of such diagrams. Based on your observations, can you tell how the solution to the previous question is generalized to the general case?

Explain how one can find point pmax in the quickhull algorithm analytically.

What is the best-case efficiency of quickhull?

Give a specific example of inputs that make quickhull run in quadratic time.

Implement quickhull in the language of your choice.

Creating decagons There are 1000 points in the plane, no three of them on the same line. Devise an algorithm to construct 100 decagons with their vertices at these points. The decagons need not be convex, but each of them has to be simple, i.e., its boundary should not cross itself, and no two decagons may have a common point.

Shortest path around There is a fenced area in the two-dimensional Eu-clidean plane in the shape of a convex polygon with vertices at points p1(x1, y1), p2(x2, y2), . . . , pn(xn, yn) (not necessarily in this order). There are two more points, a(xa, ya) and b(xb, yb) such that xa < min{x1, x2, . . . , xn} and xb > max{x1, x2, . . . , xn}. Design a reasonably efficient algorithm for comput-ing the length of the shortest path between a and b. [ORo98]

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Introduction to the Design and Analysis of Algorithms : Divide and Conquer : Convex Hull Problems by Divide and Conquer |