Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses (Q2422035)

For each discrete set \(S\) lying in an \(m\times n\) rectangle we can associate two integer vectors \(H=(h_1,\dots,h_m)\) and \(V=(v_1,\dots,v_n)\) where \(h_i\) and \(v_j\) are the numbers of cells belonging to the \(i\)th row and the \(j\)th column respectively. The problem is to reconstruct the set \(S\) from some class \(\mathcal{C}\) of discrete sets using only the vectors \(H\) and \(V\). In the paper the class of \(k\)-convex polyominoes is studied. The polyomino \(P\) is called \(k\)-convex if every pair of cells in \(P\) can be connected by an internal monotone path with at most \(k\) changes of directions. It is proved that the reconstruction problem is polynomially solvable for the class of 2-convex polyominoes.