Design and Analysis of Algorithms

Abstract Algorithms-1-Divide-and-Conquer 227

After the recursion phase is over, the algorithm must merge the two convex hulls for S

1

and S

2

into a

single convex hull for S. Conceptually, this involves locating two bridges between the hulls—line segments

connecting two points in S

1

to two points in S

2

. Once the bridges are added to connect the two hulls, the

interior segments of the sub-hulls are discarded. See Fig. 9.13 for an illustration. Finding the bridges and

discarding the inside edges requires a dual (two-dimensional) binary search, which takes time O(log n). Note

that it is not suffi cient just to place the bridges between the minima ...