2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Mar 8, 2023 at 15:24
  • $\begingroup$ It is not a constant as $ 1 \le k \le n$ $\endgroup$ Mar 8, 2023 at 15:46

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.