Tiling an Interval of the Discrete Line - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2006

Tiling an Interval of the Discrete Line

Abstract

We consider the problem of tiling a segment {0, . . . , n} of the discrete line. More precisely, we ought to characterize the structure of the patterns that tile a segment and their number. A pattern is a subset of N. A tiling pattern or tile for {0, . . . , n} is a subset A P(N) such that there exists B P(N) and such that the direct sum of A and B equals {0, . . . , n}. This problem is related to the di cult question of the decomposition in direct sums of the torus Z/nZ (proposed by Minkowski). Using combinatorial and algebraic techniques, we give a new elementary proof of Krasner factorizations. We combinatorially prove that the tiles are direct sums of some arithmetic sequences of speci c lengths. Besides, we show there are as many tiles whose smallest tilable segment is {0, . . . , n} as tiles whose smallest tilable segment is {0, . . . , d}, for all strict divisors d of n. This enables us to exhibit an optimal linear time algorithm to compute for a given pattern the smallest segment that it tiles if any, as well as a recurrence formula for counting the tiles of a segment.
Fichier principal
Vignette du fichier
OB-ER-CPM06.pdf (384.54 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00120188 , version 1 (13-12-2006)

Identifiers

Cite

Olivier Bodini, Eric Rivals. Tiling an Interval of the Discrete Line. CPM: Combinatorial Pattern Matching, Jul 2006, Barcelona, Spain. pp.117-128, ⟨10.1007/11780441_12⟩. ⟨lirmm-00120188⟩
156 View
234 Download

Altmetric

Share

More