×

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
Full Text: DOI