Finding 2 points that are k'th closest and their distance is minimal among such points with Chebyshev distance

Question

Let $p_1,p_2 \dots p_n$ be $n$ points in 2D such that $p_i= ( x_i,y_i) $

Let $d(p_i,p_j)= \max (|x_i-x_j|,|y_i-y_j|)$, or better known as Chebyshev distance. Find a point $p_i$ such that the distance to it's kth closest point is minimal among all $i$ in $\mathcal{O} ( n\log ^2 n) $. Edit: $ 1 \le k \le n$

I tried calculating all possible distances which gives me $\binom{n}{2}$ choices which means it's not the way.

Next I tried sorting all $x$ values and $ y$ values separately, then the kth closest is either 1 of the 2k closest x or 1 of the $2k$ y closest.

Those are 4 sorted sub arrays and we can merge them in $ O(n)$ to find the kth closest of each element, but then finding the minimum for $n$ elements would again result in $O(n^2)$.

Answer 1

With a 2-D orthogonal range counting query data structure, you can calculate how many points have a distance less than a specified value from a given point. Here, the query range is a square centered at the source point.

By performing binary searching on the distance, you can find the $k$-th closest distance from a point. Compute that for every point and return the smallest result.

By using a Wavelet tree, the 2-D orthogonal counting query takes $\Theta(\log n)$ time after preprocessing the points to map coordinates to the range $[1, n]$. A binary search needs $O(\log k)$ queries. Therefore, the overall problem can be solved in $O(n \log^2 n)$ time.