Maximal superpositions of horizontally convex polyominoes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theoretical Computer Science Year : 1999

Maximal superpositions of horizontally convex polyominoes


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

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



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⟩
51 View
0 Download



Gmail Facebook X LinkedIn More