Source code online books for professionals by professionals

Figure 6-7.  Worst case: eight points in a vertical slice of the middle region. The size of the slice is d×2d, and each of the 
two middle (highlighted) points represents a pair of coincident points
We’re almost done; the only remaining problems are sorting by x- and y-coordinates. We need the x-sorting to 
be able to divide the problem in equal halves at each step, and we need the y-sorting to do the linear traversal while 
merging. We can keep two arrays, one for each sorting order. We’ll be doing the recursive division on the x array, so 
that’s pretty straightforward. The handling of y isn’t quite so direct but still quite simple: When dividing the data set by 
x, we partition the y array based on x-coordinates. When combining the data, we merge them, just like in merge sort, 
thus keeping the sorting while using only linear time.
Note
 
■
  For the algorithm to work, we much return the entire subset of points, sorted, from each recursive calls.  
the filtering of points too far from the midline must be done on a copy.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
129
You can see this as a way of strengthening the induction hypothesis (as discussed in Chapter 4) in order to get the 
desired running time: Instead of only assuming we can find the closest points in smaller point sets, we also assume 
that we can get the points back sorted.
Convex Hull
Here’s another geometric problem: Imagine pounding n nails into a board and strapping a rubber band around 
them; the shape of the rubber band is a so-called convex hull for the points represented by the nails. It’s the smallest 
convex
14
 region containing the points, that is, a convex polygon with lines between the “outermost” of the points.  
See Figure 
6-8
 for an example.