On Identification in Z2 Using Translates of Given Patterns
Journal of Universal Computer Science, Vol. 9(10), pp. 1204-1219, October 2003.
http://www.jucs.org
Iiro HONKALA
Department of Mathematics
University of Turku
20014 Turku, Finland
e-mail: honkala@utu.fi
&
Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
e-mail: lobstein@infres.enst.fr
Abstract. Given a finite set of patterns, i.e., subsets of Z2, what is the best way to place translates of them in such a way that every point belongs to at least one translate and no two points belong to the same set of translates? We give some general results, and investigate the particular case when there is only a single pattern and that pattern is a square or has size at most four.