[Solved]: Linearithmic lower bound for 1-D "distinct" closest pair of points problem

Problem Detail: 

The 1-D distinct closest pair of points problem is as follows: Given a set of n distinct integer points on real line, find a pair of points with the smallest distance between them, here the distance between two points p_i and p_j is absolute difference of their values, i.e, |p_i-p_j|.

A naive way to solve this problem is to sort the points and check distance of each consecutive points in sorted order and take the minimum of such distances and this takes O(nlog n) time.

My question is can we do better than that? Can we solve it in o(n log n)(note the little-oh) time? If not, then how to show an omega(nlog n) time bound for this problem?

Note that, if the distinctness criteria was not there we could have shown a lower bound using Element Distinctness Problem.

Asked By : Sayan Bandyapadhyay

Answered By : Yuval Filmus

Given $n$ integer points $p_1,\ldots,p_n$, not necessarily distinct, consider the set of points $2np_1+1,2np_2+2,\ldots,2np_n+n$. The new points are distinct by construction, and the minimal distance is smaller than $n$ iff the original points were not distinct. So an algorithm for your problem can be used to solve element distinctness.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24115

3.2K people like this

 Download Related Notes/Documents