Further steps on the reconstruction of convex polyominoes from orthogonal projections (Q2084620)

A polyomino is a finite collection of squares having unitary size and joined edge by edge in the plane. In this paper, the authors study the problem of the reconstruction of convex polyominoes from their orthogonal projections. A polyomino \(\mathcal{P}\) is said to be convex if the convex hull of \(\mathcal{P}\), which is the intersection of all Euclidean convex sets containing \(\mathcal{P}\), does not contain any integer point outside \(\mathcal{P}\). The family of convex polyominoes is a sub-class of the \(hv\)-convex ones. We say that a polyomino \(\mathcal{P}\) is \(h\)-convex (resp. \(v\)-convex) if all cells between \(A\) and \(B\) are in \(\mathcal{P}\), for all \(A,B\in \mathcal{P}\) on the same row (resp. column). A polyomino is \(hv\)-convex if it is \(h\)-convex and \(v\)-convex at the same time. Let \(\mathcal{P}\) be a polyomino whose minimal bounding rectangle has dimension \(m\times n\). We can attach to \(\mathcal{P}\) 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 the cells of \(\mathcal{P}\) which are respectively on \(i\)-th row and \(j\)-th column. These two vectors are called respectively horizontal and vertical projections of \(\mathcal{P}\). Given two projections \(H\) and \(V\), the cells which are in common to all \(hv\)-convex polyominoes having \(H\) and \(V\) as projections form the kernel, the ones in the common external part give the shell. In \textit{E. Barcucci} et al. [Theor. Comput. Sci. 155, No. 2, 321--347 (1996; Zbl 0872.68134)] an algorithm is defined to reconstruct an \(hv\)-convex polyomino related to given horizontal and vertical projections. It consists of two distinct parts: in the first it reconstructs the kernel and the shell, in the second one it labels every cell that lies between the kernel and the shell with a Boolean variable, whose value gives the belonging of the cell to the polyomino, and it defines a \(2\)-SAT formula whose valuations determine all \(hv\)-convex polyominoes with the given projections. In [\textit{Y. Gérard}, ``About the complexity of reconstructing convex lattice sets from horizontal and vertical X-rays'', in: Tomography and applications -- discrete tomography and image reconstruction. Boston, MA: Birkhäuser (2017)] the problem of the reconstruction of convex polyominoes from two projections, considering an extension of the second part of the previous algorithm for the \(hv\)-convex polyominoes on a convex kernel has been approached. In the paper, the authors show a way to expand the kernel by adding points at specific positions of its contour without losing its convexity and using a characterization of convex polyominoes in terms of Lyndon or Christoffel words coding their contour (for a reference see [\textit{S. Brlek} et al., Pattern Recognition 42, No. 10, 2239--2246 (2009; Zbl 1176.68175)]). Finally, they provide some examples in which the addition of one or two points can cause the loss of convexity and a failure in the reconstruction process, but in such cases, they show how convexity can be recovered by adding other suitable points, which cannot be determined a priori.