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)$.