Locating patterns in the de Bruijn torus

The de Bruijn torus (or grid) problem looks to find an nn-by-mm binary matrix in which every possible jj-by-kk submatrix appears exactly once. The existence and construction of these binary matrices were determined in the 70s, with generalizations to dd-ary matrices in the 80s and 90s. However, these constructions lacked efficient decoding methods, leading to new constructions in the early 2000s. The new constructions develop cross-shaped patterns (rather than rectangular), and rely on a concept known as a half de Bruijn sequence. In this paper, we further advance this construction beyond cross-shape patterns. Furthermore, we show results for universal cycle grids, based off of the one-dimensional universal cycles introduced by Chung, Diaconis, and Graham, in the 90s. These grids have many applications such as robotic vision, location detection, and projective touch-screen displays.