Source code online books for professionals by professionals

Figure 6-3.  A set of building silhouettes and the resulting skyline
Figure 6-4.  Adding a building (dashed) to a skyline (solid)
The details of this merging aren’t all that important here. The point is that we can add a building to the skyline 
in linear time. Using simple (weak) induction, we now have our algorithm: We start with a single building and keep 
adding new ones until we’re done. And, of course, this algorithm has a quadratic running time. To improve this, we 
want to switch to strong induction—divide and conquer. We can do this by noting that merging two skylines is no 
harder than merging one building with a skyline: We just traverse the two in “lockstep,” and wherever one has a higher 
value than the other, we use the maximum, splitting horizontal line segments where needed. Using this insight, we 
have our second, improved algorithm: To create a skyline for all the buildings, first (recursively) create two skylines, 
based on half the buildings each, and then merge them. This algorithm, as I’m sure you can see, has a loglinear 
running time. Exercise 6-1 asks you to actually implement this algorithm.
The Canonical D&C Algorithm
The recursive skyline algorithm hinted at in the previous section exemplifies the prototypical way a divide-and-conquer 
algorithm works. The input is a set (perhaps a sequence) of elements; the elements are partitioned, in at most linear 
time, into two sets of roughly equal size, the algorithm is run recursively on each half, and the results are combined, 
also in at most linear time. It’s certainly possible to modify this standard form (you’ll see an important variation in the 
next section), but this schema encapsulates the core idea.
Listing 6-1 sketches out a general divide-and-conquer function. Chances are you’ll be implementing a  
custom version for each algorithm, rather than using a general function such as this, but it does illustrate how these 

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
118
algorithms work. I’m assuming here that it’s OK to simply return S in the base case; that depends on how the combine 
function works, of course.
3