Locating patterns in the de Bruijn torus

DOI10.1016/J.DISC.2015.11.015zbMATH Open1329.05161arXiv1505.04065OpenAlexW1488690765MaRDI QIDQ906472FDOQ906472

Authors: Victoria Horan, Brett Stevens 

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

universal cyclesde Bruijn toruspseudorandom arrays

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

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

Cited In (3)

• The k-centre problem for classes of cyclic words
• On the de Bruijn torus problem
• On a construction of easily decodable sub-de Bruijn arrays

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)