Source code online books for professionals by professionals

Figure 6-1.  An unbalanced decomposition, with linear division/combination cost and quadratic running time in total
Figure 6-2.  Divide and conquer: a balanced decomposition, with linear division/combination cost and loglinear 
running time in total
Let’s try to recognize this pattern in an actual problem. The skyline problem
2
 is a rather simple example. You are 
given a sorted sequence of triples (L,H,R), where L is the left x-coordinate of a building, H is its height, and R is its right 
x-coordinate. In other words, each triple represents the (rectangular) silhouette of a building, from a given vantage 
point. Your task is to construct a skyline from these individual building silhouettes.
2
Described by Udi Manber in his Introduction to Algorithms (see “References” in Chapter 4).

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
117
Figures 
6-3
 and 
6-4
 illustrate the problem. In Figure 
6-4
, a building is being added to an existing skyline. If the 
skyline is stored as a list of triples indicating the horizontal line segments, adding a new building can be done in linear 
time by (1) looking for the left coordinate of the building in the skyline sequence and (2) elevating all that are lower 
than this building, until (3) you find the right coordinate of the building. If the left and right coordinates of the new 
building are in the middle of some horizontal segments, they’ll need to be split in two. For simplicity, we can assume 
that we start with a zero-height segment covering the entire skyline.