HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Linearithmic lower bound for 1-D "distinct" closest pair of points problem

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
distinctproblemboundlowerpointsforlinearithmicclosestpair

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#24115, answer score: 7

Revisions (0)

No revisions yet.