Closest point to given point on $x$-axis

Question

There are $n$ points on 2D plane and a point $X$ on $x$-axis. I need to find the point closest to $X$. I can only think of brute force solution. Is there any way we could do this in logarithmic complexity.

Answer 1

If you know nothing about the set of points, you can't help inspecting each point, so you won't get below $\Omega(n)$ in time complexity. If you have your points preprocessed in some way, then you'd do best to sort by $x$ coordinate. Then you can look for a point with nearest $x$ coordinate in $O(\log n)$. Suppose that point has coordinates $(x_i,y_i)$. You'd still have to increase your range to cover indices $j$ in the range $x-\sqrt{(x-x_i)^2+(y-y_i)^2}\le x_j\le x+\sqrt{(x-x_i)^2+(y-y_i)^2}$. So if your points are close to the $x$ axis, this still limits your search considerably. But if your points have small $x$ coordinates but large $y$ coordinates, you gain very little from this restriction. In the worst case, without further knowledge about the set of points you have, you are still at $O(n)$.