Exact Minimum Density of Codes Identifying Vertices in the Square Grid
Yael Ben‐Haim, Simon N. Litsyn · SIAM Journal on Discrete Mathematics · 2005
An identifying code C is a subset of the vertices of the square grid ${\mathbb Z}^2$ with the property that for each element v of ${\mathbb Z}^2$, the collection of elements from C at a distance of at most one from v is nonempty and distinct from the collection of any other vertex. We prove that the minimum density of C within ${\mathbb Z}^2$ is $\frac{7}{20}$.