Math, Ad hoc, binary search... HELP

We want to find the k+1th minimum distance from a variable point x to the given set of points a_i's. Consider these points on the number line. For any arbitrary point y on the number line, the j+1th minimum distance of y from the given a_i's will be the nearest jth neighbour from y to one of the a_i's.
Taking the subsquence of all the jth neareast neighbours(among the a_i's) from y for all 1 \leq j \leq k, we can observe that the subsequence must be continuous and of length k. Let this subsequence be a_i,a_{i+1},\ldots,a_{i+k-1}
Further the kth nearest neighbour must belong to one of the end points of this subsequence.
i.e. a_i or a_{i+k-1}, and nearest distance being \min(|y-a_i|,|y-a_{i+k-1}|).
As y varies over the number line, we cover all possible continuous subsequences of length k from the a_i's and further for each subsequence, we cover all the possible distances to its corresponding neighbours.

from graph, \min(|y-a_i|,|y-a_{i+k-1}|) occurs when y=\frac{a_i+a_{i+k-1}}{2} and the corresponding minimum distance is |\frac{a_i-a_{i+k-1}}{2}|.

So just allow i to vary between 1 to n+1-k and store the minimum distances and find the required point corresponding to the kth minimum distance among all the minimum distances.

1 Like