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

Question

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?

Answer 1

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.

The only way I see to be faster than linear is to take a random sample from your list to get the right answer with a certain probability. However, I think the running time would heavily depend on the probability you would want in the list.