Maximal superpositions of horizontally convex polyominoes

Abstract : 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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 1999, 218 (2), pp.273-283. 〈10.1016/S0304-3975(98)00326-0〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01167958
Contributeur : Christophe Fiorio <>
Soumis le : jeudi 25 juin 2015 - 09:49:40
Dernière modification le : jeudi 17 mai 2018 - 12:52:03

Lien texte intégral

Identifiants

Collections

Citation

Gilles D'Andréa, Christophe Fiorio. Maximal superpositions of horizontally convex polyominoes. Theoretical Computer Science, Elsevier, 1999, 218 (2), pp.273-283. 〈10.1016/S0304-3975(98)00326-0〉. 〈lirmm-01167958〉

Partager

Métriques

Consultations de la notice

55