Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?

Question

I have got some difficulties to solve this algorithm problem.

I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, their distance is calculated as $|a-b|$. Now I need to calculated the kth largest among all possible distances of the n points in $O(n \log n)$ time using a randomized algorithm and a deterministic algorithm respectively.

To solve this problem, I begin with sorting the n points in $O(n \log n)$ time. I noticed that this problem it is similar to the quick select for the kth largest of the array. The naive approach is to calculate all possible distances and do quick select. But this takes $O(n^2)$ running time. It seems that I have to run the quick select with only necessary distances calculated. Now I have to do two things recursively:

1. partition all distances with a randomly chosen pivot, and
2. find out the numbers of distances on each side to determine which part for recursion.

There would be $O(n \log n)$ steps for the recursion. So, I have to do the two things above in $O(n)$ time. And I have difficulties with that.

Please help me. Thank you very much.

Answer 1

Given some pivot $K$, you can count the pairs with differences above it in $O(n)$, whether you use a random pivot or binary search.

The pairs form a kind of uneven grid in the plane, and you can search diagonally along the line $y = K+x$ to find the border between $x_j - x_i \le K$ and $x_j - x_i \gt K$ in $O(n)$ as follows (Bresenham's Line Drawing Algorithm):

1. Start at the y axis and find minimum $j$ so that $x_j - x_0 > K$

2. $Count = n-j+1$

3. For $i = 1$ to $n-1$ do

   While $x_j - x_i < K$, $j = j+1$

   If $j=n$ break

   $Count = Count + n - j + 1$

(There are some adjustments for when K is larger than the range, but the main idea is here.)

Basically you move right and then slide $j$ up until you cross the line, then add all the entries above that point to the count. As you continue right you're always at or above the $j$ you used in the previous column, so you do $O(n)$ pair tests for the whole scan.

Answer 2

Given are numbers $x_1$ to $x_n$. We assume they are sorted in non-decreasing order (since they can be sorted in O (n log n)). We assume that the distance d (i, j) between $x_i$ and $x_j$ is calculated in constant time as $x_j - x_i$, if j ≥ i, with fixed precision. When we are looking for "the k-th largest distance", we look for a pair (i, j), i ≤ j, such that d (i', j') ≥ d (i, j) for exactly k pairs (i', j'), i' ≤ j'. The solution may be not unique. Assume 1 ≤ k ≤ n (n+1) / 2, otherwise there is no solution.

Subproblem: Given d ≥ 0, find how many pairs (i, j), i ≤ j, there are with d (i, j) ≥ d (we will want to find d such that this number is k). This can be done in linear time: For every i, 1 ≤ i ≤ n, let $j_i$ be the smallest j, i ≤ j ≤ n, such that d (i, j) ≥ d, or $j_i = n + 1$ if no such j exists. We get the number of pairs by adding $n - j_i + 1$ for 1 ≤ i ≤ n.

To find $j_i$, we let $j_i = 1$ if i = 1, and $j_i = max (i, j_{i-1})$ if i > 1. Then as long as $j_i ≤ n$ and $d (i, j_i) < d$ we increase $j_i$ by 1. This is all done in linear time, because we don't increase the various values of $j_i$ more than n times in total.

Main problem: We know that 0 ≤ d (i, j) ≤ d (1, n). So we just perform a binary search to find d, 0 ≤ d ≤ d (1, n) such that exactly k values d (i, j) are ≤ d: Start with low = 0, high = d (1, n). If high = 0 then all distances are 0, and any (i, j), i ≤ j, is a solution.

Otherwise repeat as long as there are possible values between low and high: Pick mid between low and high with about equal numbers of values low < mid and mid < high (if the distances are floating-point numbers then mid is usually not (low + high) / 2). Find how many pairs (i, j) there are with d (i, j) ≥ mid. If that number is ≥ k then let high = mid, otherwise let low = mid.

Eventually low and high are consecutive possible values. If there are less than k pairs d (i, j) ≥ high then let d = low, otherwise d = hi. Use the (subproblem) algorithm above to find the pairs d (i, j) ≥ d; that algorithm will also find (i, j) with d (i, j) = d, and that's the solution.