Given a set of points, find the one closest to a given point
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.