De Bruijn Shapes: Theory and Instances

Abstract

Working with ever-increasing datasets can be time-consuming and resource-intensive. De Bruijn sequences, which allow you to visit all conceivable combinations of data exactly once, may be an attractive choice for trying to process the related items inside those datasets in the best feasible way. These sequences are unidimensional, but the same approach can be extended to include more dimensions, such as de Bruijn tori for bidimensional patterns or de Bruijn 3D-hypertori for tridimensional patterns, which can be further developed to infinite dimensions. The objectives of this study are to expose the main features of all those de Bruijn shapes, along with some relevant particular instances, which may be useful in pattern location in one, two and three dimensions. De Bruijn sequences have been extended to higher dimensions, generating de Bruijn hypertori, and presenting a generic template for the most common condition to achieve such shapes.