nth closest point with integer coordinates to a given point I am trying to find the nth closest point to a given point in 2 dimensions. The given point can have any coordinates, but the result must x and y coordinates that are integers.
It is possible to do this by finding all points within a radius of n (actually $\sqrt n$ or something), building a heap and searching for the n closest points, but is there a faster way to do this? I do not need the n closest points, only the nth closest.
 A: If you just want the $n^{\text{th}}$ closest point, the obvious improvement to make is to still take the $\mathcal O(n)$ points within distance $\sqrt n$ of the given point, but then use a linear-time selection algorithm (e.g. Quickselect) to choose the $n^{\text{th}}$ value.
Beyond that, we can also make use of the fact that a circle of radius $r$ with integer center contains approximately $\pi r^2$ integer points, with error that Gauss bounded by $2\sqrt2 \pi r$ (the Gauss circle problem) and that we now have slightly better bounds for. 
So we can, fairly precisely, choose a circular region that's guaranteed to have $n$ integer points in it: e.g., the union of four circles centered at the four nearest integer points near the given point, with radius $r$ such that $\pi r^2 - 2\sqrt2 \pi r > n$. We can also, similarly, find a smaller region that's guaranteed to not contain the $n^{\text{th}}$ closest point, leaving probably $\mathcal O(\sqrt n)$ or so candidate points.
Unfortunately, while this may speed up our search, it won't push it below $\mathcal O(n)$ time complexity, because we still need to figure out exactly how many points in the smaller region we're throwing away before we can rank the actually-viable points.
But if we could exactly count the number of integer points in a circle of radius $r$ (we can even assume it has integer center) in time $o(r^2)$, then we could use this idea to speed up the algorithm even further.
