Maximizing the number of lattice points in a circle of radius $r$ placed on a lattice - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:25:46Z http://mathoverflow.net/feeds/question/110238 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat Maximizing the number of lattice points in a circle of radius $r$ placed on a lattice unknown (yahoo) 2012-10-21T15:07:10Z 2012-10-21T16:58:06Z <p>I have a circle of radius $r$, and I wish to place this circle of a $Z^2$ integer lattice or an $A_2$ hexagonal lattice s.t. I maximize the number of lattice points within or along the contour of the circle. </p> <p>Trivially, for $r &lt; \frac{R}{2}$, where $R$ is the smallest spacing between lattice points, it will be optimal to center the circle on a lattice point. However, is there an optimal position within the fundamental unit of either lattice if $r \geq T$, where $T$ is some threshold value?</p> <p>Taking a guess for the $Z^2$ integer lattice, I'd say that centering the circle on a lattice point will be optimal for $r \geq \sqrt(2)$ and $r &lt; \frac{1}{2}$. For $\frac{\sqrt(2)}{2} \leq r &lt; \sqrt(2)$, the optimal position for the circle will be in the center of the square unit cell of the lattice (allowing coverage of four lattice points), and for $\frac{1}{2} \leq r &lt; \frac{\sqrt(2)}{2}$, the optimal position will between two lattice points separated by the smallest possible inter-point distance (i.e. the unit distance) s.t. the circle covers these two points. However, I don't know how to prove this. </p> <p>For an $A_2$ hexagonal lattice, we know for $r &lt; \frac{1}{2}$ that centering the circle on a lattice point will be optimal (allowing coverage of a single lattice point), and can guess that the next optimal position will be between two lattice points separated by the smallest possible inter-point distance (i.e. the unit distance) for $\frac{1}{2} \leq r &lt; \frac{1}{\sqrt{3}}$ (covering two lattice points), then at the barycenter of an equilateral triangle cell in the lattice for $\frac{1}{\sqrt{3}} \leq r &lt; \frac{\sqrt{3}}{2}$ (covering three lattice points), then, it seems, back between two lattice points separated by the unit distance for $\frac{\sqrt{3}}{2} \leq r &lt; 1$ (covering four lattice points), then back to the center of the lattice for $r = 1$ (covering seven lattice points)? Is it optimal to remain centered on a lattice point for $r > 1$?</p> <hr> <p>In a previous question ( <a href="http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r" rel="nofollow">http://mathoverflow.net/questions/110186/an-exact-counting-solution-for-the-number-of-points-within-a-circle-of-radius-r</a> ) I noted the exact counting solution for the number of points contained or along the contour of a circle of radius $r$ centered on a lattice point in a $Z^2$ integer lattice, and Yoav Kallus provided an exact counting solution for the $A_2$ hexagonal lattice. </p> <p>We can note that, if $D$ is the largest spacing between lattice points in an arbitrary lattice ($D = \sqrt(2)$ on a $Z^2$ integer lattice and $D = 1$ on an $A_2$ hexagonal lattice), then a circle of radius $(r + D)$ centered on a lattice point will always cover more lattice points than a circle of radius $r$ centered at arbitrary coordinates. </p> http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat/110248#110248 Answer by Michael Biro for Maximizing the number of lattice points in a circle of radius $r$ placed on a lattice Michael Biro 2012-10-21T16:58:06Z 2012-10-21T16:58:06Z <p>I want to say that by symmetry, the only relevant centers are lattice points, midpoints of square edges, and centers of squares, and that they each are optimal for varying values of $r > \sqrt(2)$.</p> <p>If we take $r = 1.55$, then the circle centered at a lattice point contains $9$ lattice points, the circle centered on a square contains $4$ lattice points, and the circle centered on an edge midpoint contains $8$ lattice points. Winner: Center on a lattice point.</p> <p>If we take $r = 1.6$, then the circle centered at a lattice point contains $9$ lattice points, the circle centered on a square contains $12$ lattice points, and the circle centered on an edge midpoint contains $8$ lattice points. Winner: Center at the center of a lattice square.</p> <p>If we take $r = 2.1$, then the circle centered on a lattice point contains $13$ lattice points, while the circle centered on a square contains $12$ lattice points, and the circle centered on an edge midpoint contains $16$ lattice points. Winner: Center at the midpoint of a lattice edge.</p> <p>I suspect that the three possible centers cycle through as optimal solutions.</p>