Locating patterns in the de Bruijn torus

DOI10.1016/J.DISC.2015.11.015MaRDI QIDQ906472zbMATH OpenOpenAlexFDO

Authors Victoria Horan, Brett Stevens

Publication date 21 January 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04065

zbMATH Keywords

universal cyclesde Bruijn toruspseudorandom arrays

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: The de Bruijn torus (or grid) problem looks to find an $n$-by-$m$ binary matrix in which every possible $j$-by-$k$ submatrix appears exactly once. The existence and construction of these binary matrices was determined in the 70's, with generalizations to $d$-ary matrices in the 80's and 90's. However, these constructions lacked efficient decoding methods, leading to new constructions in the early 2000's. 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 90's. These grids have many applications such as robotic vision, location detection, and projective touch-screen displays.

Recommendations

• On the de Bruijn torus problem
• A note on binary arrays with a certain window property (Corresp.)
• New constructions for De Bruijn tori
• On a construction of easily decodable sub-de Bruijn arrays
• scientific article; zbMATH DE number 718858

Cites work

• Computing \(k\)-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• Constructions for perfect maps and pseudorandom arrays
• De Bruijn sequences with varying combs
• Generalized de Bruijn cycles
• Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner
• New constructions for De Bruijn tori
• On the existence of de Bruijn tori with two by two windows
• Research problems on Gray codes and universal cycles
• Simple and Robust Binary Self-Location Patterns
• Universal cycles for combinatorial structures
• Universal cycles of \(k\)-subsets and \(k\)-permutations

Cited in

(4)

• On a construction of easily decodable sub-de Bruijn arrays
• Using alternating de Bruijn sequences to construct de Bruijn tori
• The k-centre problem for classes of cyclic words
• On the de Bruijn torus problem

This page was built for publication: Locating patterns in the de Bruijn torus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906472)