Page 555 - Discrete Mathematics and Its Applications

534 8 / Advanced Counting Techniques

d/2 d/2 d/2 d/2

d/2
At most eight points, including p,
can lie in or on the 2d d rectangle
centered at because at most one
point can lie in or on each of the
d/2 eight (d/2) (d/2) squares.
d/ 2
p

FIGURE 2 Showing That There Are at Most Seven Other Points to Consider for Each
Point in the Strip.

each recursive step, we form a subset of the points in the region sorted by their y coordinates
from the already sorted set of all points sorted by their y coordinates, which can be done
with O(n) comparisons.
Beginning with a point in the strip with the smallest y coordinate, we successively examine
each point in the strip, computing the distance between this point and all other points in the strip
that have larger y coordinates that could lie at a distance less than d from this point. Note that
to examine a point p, we need only consider the distances between p and points in the set that
lie within the rectangle of height d and width 2d with p on its base and with vertical sides at
distance d from .
We can show that there are at most eight points from the set, including p, in or on this 2d × d
rectangle. To see this, note that there can be at most one point in each of the eight d/2 × d/2
squares shown in Figure 2. This follows because the farthest apart points can be on or within
√
one of these squares is the diagonal length d/ 2 (which can be found using the Pythagorean
theorem), which is less than d, and each of these d/2 × d/2 squares lies entirely within the left
region or the right region. This means that at this stage we need only compare at most seven
distances, the distances between p and the seven or fewer other points in or on the rectangle,
with d.
Because the total number of points in the strip of width 2d does not exceed n (the total
number of points in the set), at most 7n distances need to be compared with d to find the
minimum distance between points. That is, there are only 7n possible distances that could be
less than d. Consequently, once the merge sort has been used to sort the pairs according to their
x coordinates and according to their y coordinates, we find that the increasing function f (n)
satisfying the recurrence relation

f (n) = 2f (n/2) + 7n,

where f(2) = 1, exceeds the number of comparisons needed to solve the closest-pair problem
for n points. By the master theorem (Theorem 2), it follows that f (n) is O(n log n).The two sorts
of points by their x coordinates and by their y coordinates each can be done using O(n log n)
comparisons, by using the merge sort, and the sorted subsets of these coordinates at each of the
O(log n) steps of the algorithm can be done using O(n) comparisons each. Thus, we find that
the closest-pair problem can be solved using O(n log n) comparisons. ▲