3
$\begingroup$

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.

Trivially, for $r < \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?

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 < \frac{1}{2}$. For $\frac{\sqrt(2)}{2} \leq r < \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 < \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.

For an $A_2$ hexagonal lattice, we know for $r < \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 < \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 < \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 < 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$?

In a previous question ( An exact counting solution for the number of points within a circle of radius $r$ centered on a lattice point in a $A_2$ hexagonal lattice ) 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.

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

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.

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.

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.

I suspect that the three possible centers cycle through as optimal solutions.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Michael Biro "I want to say that by symmetry, the only relevant centers are lattice points, midpoints of square edges, and centers of squares..." right, I think that makes a lot of sense... but is there any way to make this statement rigorous? $\endgroup$
    – user27203
    Commented Oct 21, 2012 at 17:37
  • $\begingroup$ @Michael Biro If a circle of radius $r$ were to execute something like a Brownian motion on a lattice, would we really only expect peaks when its center drifts over a small set of points in the fundamental unit of the Z^2 or A^2 lattices? $\endgroup$
    – user27203
    Commented Oct 21, 2012 at 18:04
  • $\begingroup$ Ahem, peaks in terms of the number of lattice points internal to the circle. $\endgroup$
    – user27203
    Commented Oct 21, 2012 at 18:05
  • $\begingroup$ Depending on what you mean by small, I think so. Given $r$ and a square, look at all lattice points that are in the circle for some center in the square but not in the circle for a different center. There are $O(r)$ of these points and if you take the arrangement of radius $r$ circles centered at these lattice points, we get $O(r^2)$ faces, where two circles of radius $r$ with centers in the same face in the square contain the same lattice points. So, there are at most $O(r^2)$ different values the function can take, even without looking for peaks, and most small movements won't matter at all. $\endgroup$
    – Michael Biro
    Commented Oct 21, 2012 at 19:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .