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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01167958
Contributor : Christophe Fiorio <>
Submitted on : Thursday, June 25, 2015 - 9:49:40 AM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

114