The Algorithm Design Manual Second Edition

9.2.1

Closest Pair

The closest pair problem asks to find the pair of numbers within a set that have

the smallest difference between them. We can make it a decision problem by asking

if this value is less than some threshold:

Input: A set S of n numbers, and threshold t.

Output: Is there a pair s

i

, s

j

∈ S such that |s

i

− s

j

| ≤ t?

The closest pair is a simple application of sorting, since the closest pair must

be neighbors after sorting. This gives the following algorithm:

CloseEnoughPair(S,t)

Sort S.

Is min

1

≤i

|s

i

− s

i+1

| ≤ t?

time is the time needed to perform the reduction plus that to solve the b instance.

---

320

9 .

I N T R A C T A B L E P R O B L E M S A N D A P P R O X I M A T I O N A L G O R I T H M S

There are several things to note about this simple reduction.

1. The decision version captured what is interesting about the problem, meaning

it is no easier than finding the actual closest pair.

2. The complexity of this algorithm depends upon the complexity of sorting.

Use an O(n log n) algorithm to sort, and it takes O(n log n + n) to find the

closest pair.

3. This reduction and the fact that there is an Ω(n log n) lower bound on sorting

does not prove that a close-enough pair must take Ω(n log n) time in the worst

case. Perhaps this is just a slow algorithm for a close-enough pair, and there

is a faster one lurking somewhere?

4. On the other hand, if we knew that a close-enough pair required Ω(n log n)

time to solve in the worst case, this reduction would suffice to prove that

sorting couldn’t be solved any faster than Ω(n log n) because that would

imply a faster algorithm for a close-enough pair.