I just posted a question at MathOverflow ( https://mathoverflow.net/questions/292407/packing-points-in-a-lattice) that may interest some of you: Let $L$ be the square or triangular lattice in the plane, with nearest neighbors having distance 1. Has anyone studied the problem of finding the maximum (okay, supremum) density achieved by a subset of $L$ in which no two points are closer together than distance $d$, for various values of $d$? In some ways this is more natural for the triangular lattice than for the square lattice, since in the off-lattice version of the problem the answer is a triangular lattice of side-length $d$. (Or, turning this around, the problem is more interesting on a square lattice than a triangular lattice because of incommensurability between the lattice $L$ and the subset of $L$ that achieves maximum density, rescaled, when $d$ is large.) As a concrete example, consider the square grid with $d=\sqrt{5}$. A tilted square lattice with density 1/5 avoids distances $<d$. Dually, we can cover $L$ with sets of the form $\{(i,j), (i-1,j), (i+1,j), (i,j-1), (i,j+1)\}$, none of which can contain more than a single point in common with a subset of the grid that avoids distances less than $\sqrt{5}$. So the maximum density is 1/5. It is not clear to me that for every $d$ the supremum is achieved by a periodic packing. Certainly the existence of Wang tiles suggests that a suitably broad version of the packing problem will run afoul of decideability issues. But approximate balls are very different from Wang tiles, so my instinct is that only periodic optima occur. Pointers to the literature would be appreciated. Also, it seems to me that a form of linear programming duality could be used to establish upper bounds on density, generalizing the argument I give above for $d=\sqrt{5}$ on the square lattice. Jim Propp