Well-Spaced Labelings of Points in Rectangular Grids
Jeffrey C. Lagarias · SIAM Journal on Discrete Mathematics · 2000
We describe methods to label the M 1 × M 2 grid with the integers 1 to M 1 M 2 so that any K consecutively labeled cells are relatively far apart in the grid in the Manhattan metric. Constructions of such labelings are given which are nearly optimal in a range of conditions. Such labelings can be used in addressing schemes for storing data on two-dimensional arrays that include randomly located "blobs" of defective cells. The data can be precoded using block error-correcting codes before storage, and the usefulness of well-spaced points is to decrease the probability of "burst" errors which cannot be corrected. Possible applications include the storage of speech or music on low-quality memory chips and in "holographic memories" to store bit-mapped data. More generally, we present a general family of mappings of the integers 1 to M 1 M 2 . . . M d onto the d-dimensional grid of size M 1 × M 2 × . . . × M d , called mixed radix vector mappings. These mappings give labelings whenever they are one to one. We give a sufficient condition for these mappings to be one to one, which is easy to verify in many cases.