Polyomino decomposition

Hugo Tremblay

University of Ottawa

In this talk, we study prime and composed polyominoes. This concept arises naturally from a composition operator defined on a particular type of morphism called parallelogram morphism. An obvious question when dealing with prime objects is wether there is a theorem similar to the fundamental theorem of arithmetic, i.e. any object admits a unique decomposition into prime ones. We prove that such a factorization exists for all polyomino without hole by giving a polynomial decomposition algorithm. Then, we briefly discuss the unicity of such a decomposition.

This is a joint work with Alexandre Blondin Massé from UQÀM.