Source code online books for professionals by professionals

n
). Take the logarithm and Bob’s your uncle.
13
 Now, we derived the bound for the worst case; using 
information theory (which I won’t go into here), it is, in fact, possible to show that this bound holds also in the average 
case. In other words, in a very real sense, unless we know something substantial about the value range or distribution 
of our data, loglinear is the best we can do.
Three More Examples
Before wrapping up this chapter with a slightly advanced (and optional) section, here are three examples for the 
road. The first two deal with computational geometry (where the divide-and-conquer strategy is frequently useful), 
while the last one is a relatively simple problem (with some interesting twists) on a sequence of numbers. I have only 
sketched the solutions, because the point is mainly to illustrate the design principle.
Closest Pair
The problem: You have a set of points in the plane, and you want to find the two that are closest to each other. The first 
idea that springs to mind is, perhaps, to use brute force: For each point, check all the others, or, at least, the ones we 
haven’t looked at yet. This is, by the handshake sum, a quadratic algorithm, of course. Using divide and conquer, we 
can get that down to loglinear.
This is a rather nifty problem, so if you’re into puzzle-solving, you might want to try to solve it for yourself 
before reading my explanation. The fact that you should use divide and conquer (and that the resulting algorithm is 
loglinear) is a strong hint, but the solution is by no means obvious.
11
Real numbers usually aren’t all that arbitrary, of course. As long as your numbers use a fixed number of bits, you can use radix 
sort (mentioned in Chapter 4) and sort the values in linear time.
12
I think that’s so cool, I wanted to add an exclamation mark after the sentence ... but I guess that might have been a bit confusing, 
given the subject matter.
13
Actually, the approximation isn’t asymptotic in nature. If you want the details, you’ll find them in any good mathematics 
reference.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
128
The structure of the algorithm follows almost directly from the (merge sort-like) loglinear divide-and-conquer 
schema: We’ll divide the points into two subsets, recursively find the closest pair in each, and then—in linear time—merge 
the results. By the power of induction/recursion (and the divide-and-conquer schema), we have now reduce the problem 
to this merging operation. But we can peel away even a bit more before we engage our creativity: The result of the merge 
must be either (1) the closest pair from the left side, (2) the closest pair on the right side, or (3) a pair consisting of one 
point from either side. In other words, what we need to do is find the closest pair “straddling” the division line. While doing 
this, we also have an upper limit to the distance involved (the minimum of the closest pairs from the left and right sides).
Having drilled down to the essence of the problem, let’s look at how bad things can get. Let’s say, for the moment, 
that we have sorted all points in the middle region (of width 2d) by their y-coordinate. We then want to go through 
them in order, considering other points to see whether we find any points closer than d (the smallest distance found 
so far). For each point, how many other “neighbors” must we consider?
This is where the crucial insight of the solution enters the picture: on either side of the midline, we know that all 
points are at least a distance of d apart. Because what we’re looking for is a pair at most a distance apart, straddling the 
midline, we need to consider only a vertical slice of height d (and width 2d) at any one time. And how many points can 
fit inside this region?
Figure 
6-7
 illustrates the situation. We have no lower bounds on the distances between left and right, so in the 
worst case, we may have coinciding points on the middle line (highlighted). Beyond that, it’s quite easy to show that  
at most four points with a minimum distance of d can fit inside a d×d square, which we have on either side; see 
Exercise 6-15. This means that we need to consider at most eight points in total in such a slice, which means our 
current point at most needs to be compared to its next seven neighbors. (Actually, it’s sufficient to consider the five 
next neighbors; see Exercise 6-16.)