Skip to Main content Skip to Navigation
Journal articles

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
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




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⟩



Record views