5
$\begingroup$

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.

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ It's awesome. I really appreciate. @Yuval. $\endgroup$ Apr 25, 2014 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.