Maximum and minimum points overlapped by moving circle on square grid.

Question

We have a square grid, of points spaced evenly at distance $u$, like on a math notebook.
We have a moving circle of radius $r$, like a coin sliding around on it. A decent approximation of points overlapped by the circle is $$ c\frac{\mathrm{Area}}{u^2} = \pi\cdot\Big(\frac{u}{r}\Big)^{\!2}. $$ So far so good. This falls apart on the edge cases, especially on sparse grids:

Under those conditions, pMin is 3, pMax is 6, and my approximation is 4. Not a great estimate. Feel free to play with the online toy here.

So, is there any way to reliably, mathematically find pMin, pMax, and maybe some sort of average? An intuition to me would be that there are key discrete points in between those points, which is what I'll be working on.
Thank you!

Answer 1

Let's fix the grid spacing to be $1$ and introduce a function $n(r,x,y)$, which is the number of points that lie inside the circle (including boundary) of radius $r$ with the center at $(x,y)$.

Then we can denote $n_1(r)=\min\limits_{x,y}n(r,x,y)$ the minimal number of points over all possible positions and $n_2(r)=\max\limits_{x,y}n(r,x,y)$, the maximal number.

Let's think of how the functions $n_1(r)$ and $n_2(r)$ look. The first idea is that both functions are monotonous (you can prove it yourself). In addition, since both functions are integer-valued, they are the sum of step functions of form $\theta(r-r_i)$. The idea is to find the radii $r_i$ at which they increase.

The second idea is that the increments will occur at the radius of the circumcircle of some 3 grid points. That allows us to actually go over all possible triplets of grid points, find radii of circumcircles and the number of points they include. So we can construct this function algorithmically:

We see that most of the time $\pi r^2$ is indeed a very good approximation, but at certain radii, the discrepancy can be quite significant. These radii are of circles that go through surprisingly many grid points.

Finally, the discrepancy between $n_1$/$n_2$ and the estimation $\pi r^2$ seems to grow linearly. Which is very similar to Gauss's estimation in a similar circle lattice point problem: