Maximal superpositions of horizontally convex polyominoes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 1999

Maximal superpositions of horizontally convex polyominoes

Résumé

Horizontally convex polyominoes are finite discrete sets of simply connected elementary cells, such that all of their rows are connected. The problem is to find the best matching between two horizontally convex polyominoes. So, we look for a position of the second polyomino relative to the first one, called a translation, such that the overlapping surface of the two polyominoes is maximal. In this paper, we present an optimal algorithm computing the overlapping surface for all possible translations. Then, we can exhibit the maximal superposition and the related translations.

Dates et versions

lirmm-01167958 , version 1 (25-06-2015)

Identifiants

Citer

Gilles d'Andréa, Christophe Fiorio. Maximal superpositions of horizontally convex polyominoes. Theoretical Computer Science, 1999, 218 (2), pp.273-283. ⟨10.1016/S0304-3975(98)00326-0⟩. ⟨lirmm-01167958⟩
52 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More