How to cover maximum points with a fixed length line segment?

Question

The problem is defined as:

Given a set of $N$ points $(x_1, x_2, x_3, \ldots, x_n)$ and $L$ the fixed length of a segment.

Find the number of maximum points which you can cover with a segment line of length $L$.

Ranges

$1 \leq N \leq 100 000$

$1 \leq L \leq 10^{10}$

$0 \leq x_i \leq 10^{10}$

I call sub-optimal ranges, ranges which are in the form $[x_n,x_n+L]$. The optimal range is the one which contains the maximum points of all ranges.

I've tried to consider the problem using that algorithm (pseudo-code):

Let be S, the set which contains all the N points.
Let be R, the set which contains ranges.
Let be maxPoints, the number of maximum points that we can have (set it to 0).
For all points p I have in my set S
     Store in R the range $[p, p+L]$
For all ranges r I have in my set R
     nPoints = 0
     For all points p I have in my set S
         If the point p is in the range r, then increment nPoints
     maxPoints = maximum value between maxPoints and nPoints
Display maxPoints

I think that the complexity of this algorithm is $O(N^{2})$, is there a way to make it faster? And is it really correct (in the sense, that it solves all cases of this problem).

Answer 1

You haven't explained how to implement how many there is point in the range r. You do this operation N times, so unless it takes $O(1)$, your algorithm won't be $O(N)$.

There is a simple algorithm that runs in time $O(N\log N)$:

1. Sort the input points.
2. Go over all the points in order, maintaining a data structure keeping track of the points at distance at most $L$ from the current point.

You can implement each iteration of the second step in amortized $O(\log N)$ using a balanced binary search tree.

Can we do it asymptotically faster? In many restriction computation model, the problem of element uniqueness (given a list of integers, determine whether they are all unique) requires $\Omega(N\log N)$ operations. Since element uniqueness reduces to your problem, in these models your problem requires $\Omega(N\log N)$, so the algorithm broadly outlined above is asymptotically optimal.

Of course, in practice you might benefit from algorithms which are more sensitive to the input distributions. In fact, assuming the answer is $M$, the algorithm outlined above runs in time $O(N\log M)$. If you expect $M$ to be very small, it might be worthwhile to use a list rather than a balanced binary search tree.