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

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

• Is $k$ a constant, or part of the input (and therefore could be $\Omega(n)$)? If it is a constant, a range tree could be useful, since the unit sphere of the Chebyshev distance is a square. Mar 8 at 15:24
• It is not a constant as $1 \le k \le n$ Mar 8 at 15:46

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.