Exact minimum density of codes identifying vertices in the square grid. (English) Zbl 1085.94026
Summary: 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}\).
MSC:
94B99 | Theory of error-correcting codes and error-detecting codes |
11H31 | Lattice packing and covering (number-theoretic aspects) |
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
05B40 | Combinatorial aspects of packing and covering |