# Given a set of points, find the one closest to a given point

So, I'm given an arbitrary set of points $(p_1, p_2, p_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me.

I need to write code that will take in a point, $p_0$, and will find the point $(p_1, p_2, p_3\ldots)$ closet to $p_0$. This will of course be found my minimizing $R$ in $R^2 = (x - x_0)^2 + (y - y_0)^2$.

I could implement this easily if I linearly search the list of points each time (always $O(n)$ complexity). However, I would prefer something that could be an average of $\log(n)$ complexity. Does anyone have a suggestion on a search algorithm?

• Do you wish to test several points $p_0$ with the same set of points $p_1,p_2,\ldots$? In that case, we can spend $O(n\log n)$ time to build a data structure such that all later queries will take $O(\log n)$. Otherwise, you'll have to spend linear time at least. – Discrete lizard Feb 2 '18 at 14:44
• en.wikipedia.org/wiki/K-d_tree – D.W. Feb 2 '18 at 16:54

If we make no assumptions on input and want an exact answer to the question what the minimum distance is to $p_0$, any algorithm must take at least $\Omega(n)$ time in the worst case. To see this, suppose $p_0$ is in your input points. In the worst case, the final point we see in our list is this point! So we must inspect all our input points and hence take $\Omega(n)$ time.
For the same reason, an approximation algorithm must also use $\Omega(n)$ time, as the difference in distance to $p_0$ between the inspected points in the list and the points we haven't inspected yet may be arbitrarily large.