Reconstruction and Enumeration of hv-Convex Polyominoes with Given Horizontal Projection

摘要

Enumeration and reconstruction of certain types of polyominoes, according to several parameters, are frequently studied problems in combinatorial image processing. Polyominoes with fixed projections play an important role in discrete tomography. In this paper, we provide a linear-time algorithm for reconstructing hv-convex polyominoes with minimal number of columns satisfying a given horizontal projection. The method can be easily modified to get solutions with any given number of columns. We also describe a direct formula for calculating the number of solutions with any number of columns, and a recursive formula for fixed number of columns.