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

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!

• This makes me think of maximising packing and decision maths. Also, you could do this with any shape, not just a circle. But circle, square and right-angled triangle will probably be easiest to deal with. You could also have an equilateral triangular grid of dots, and you could take this really far and have a grid of dots with any pattern, not just a square grid. Pretty cool the potential here. – Adam Rubinson Oct 17 '19 at 12:41
• Also, shouldn't it be $\pi (\frac{r}{u})^2$ ? – Adam Rubinson Oct 17 '19 at 12:51
• @AdamRubinson I'm working on it! I'll be working with uniform random, poisson, hex grids.. just for interest. My game will use the square grid but I'm curious about other distributions. – Alex Mitan Oct 17 '19 at 20:04

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: 