CODEWITHSUNDEEP
algorithmsortingproof
davik
davik

Reputation: 695

Can we show that finding the (1-D) closest pair has to be at least n log n?

How can we show that using comparison methods only, 1-D closest pair is Ω(n log n)? I think that the only reasonable way is to somehow show an equivalence to sorting, but I cannot see how. Can someone shed light on this? In this problem, assume the list contains distinct elements only.

Upvotes: 2

Views: 99

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65488

You want a lower bound for the linear decision tree model, because no algorithm that just compares the points without subtracting to find a distance has a hope of working. The classic approach to getting lower bounds in this model is to show that the linear decision tree has to have at least a certain number of leaves, which given binary branches, implies a minimum height.

The relevant property of linear tests is that, if two inputs (i.e., n-dimensional vectors) result in the same decision tree outcomes, then all inputs on the line segment joining them do too.

Consider the easier problem of deciding whether the closest pair is at distance less than 1. I claim that all permutations of the integers 1..n must end up in different decision tree leaves. Otherwise, consider two permutations that end up in the same leaf. Since the permutations are different, there exist i and j such that the ith and jth entries compare differently in the two permutations. This implies by the intermediate value theorem that there exists an intermediate input where they are at distance less than 1, which is impossible, because everything that ends up in the leaf must have minimum distance 1.

With at least n! leaves, the tree must have height at least lg n! = Omega(n log n).

See http://otfried.org/courses/cs493fall2012/algebraic-tree.pdf among many other sets of lecture notes for a longer write-up; this is a standard topic in computational geometry courses.

Upvotes: 3

Related Questions