Further steps on the reconstruction of convex polyominoes from orthogonal projections
type: Item
instance of: scholarly article
title: Further steps on the reconstruction of convex polyominoes from orthogonal projections
author: Paolo Dulio
author: Lama Tarsissi
author: L. Vuillon
author: Andrea Frosini
author: S. Rinaldi
published in: Journal of Combinatorial Optimization
publication date: 2022-10-18T00:00:00Z
review text: 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 a…
reviewed by: Francesco Navarra
Mathematics Subject Classification ID: 05B50
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52A41
zbMATH DE Number: 7603275
zbMATH Keywords: digital convexity
zbMATH Keywords: discrete geometry
zbMATH Keywords: discrete tomography
zbMATH Keywords: reconstruction problem
MaRDI profile type: Publication
full work available at URL: s10878-021-00751-z
OpenAlex ID: W3161265967
cites work: Reconstructing convex polyominoes from horizontal and vertical projections
cites work: X-rays characterizing some classes of discrete sets
cites work: Sturmian words, Lyndon words and trees
cites work: Asymptotic Analysis and Random Sampling of Digitally Convex Polyominoes
cites work: Certain words on the real projective line
cites work: A Tomographical Interpretation of a Sufficient Condition on h-Graphical Sequences
cites work: Lyndon + Christoffel = digitally convex
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: Reconstruction of 4- and 8-connected convex discrete sets from row and column projections
cites work: Fast Filling Operations Used in the Reconstruction of Convex Lattice Sets
cites work: \(\alpha\)-words and factors of characteristic sequences
cites work: Sturmian words: structure, combinatorics, and their arithmetics
cites work: Some combinatorial properties of Sturmian words
cites work: The number of convex polyominoes reconstructible from their orthogonal projections
cites work: A geometrical characterization of regions of uniqueness and applications to discrete tomography
cites work: Geometrical Characterization of the Uniqueness Regions Under Special Sets of Three Directions in Discrete Tomography
cites work: First steps in the algorithmic reconstruction of digital convex sets
cites work: Regions of Uniqueness Quickly Reconstructed by Three Directions in Discrete Tomography
cites work: Factorizing words over an ordered alphabet
cites work: Q4475319
cites work: Uniqueness Theorems for Periodic Functions
cites work: On the Degree Sequences of Uniform Hypergraphs
cites work: A theorem on flows in networks
cites work: Discrete tomography: Determination of finite sets by X-rays
cites work: On the computational complexity of reconstructing lattice sets from their \(X\)-rays
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Polygons, polyominoes and polycubes
cites work: On periodic properties of circular words
cites work: Discrete tomography. Foundations, algorithms, and applications
cites work: Three-dimensional Statistical Data Security Problems
cites work: Q4341774
cites work: Q3851094
cites work: Switching components and the ambiguity problem in the reconstruction of pictures from their projections
DOI: 10.1007/S10878-021-00751-Z
Recommended article: Reconstruction of convex polyominoes from orthogonal projections of their contours
Recommended article: Q5317670
Recommended article: Q4473991
Recommended article: The reconstruction of polyominoes from their orthogonal projections
Recommended article: The Reconstruction of Some 3D Convex Polyominoes from Orthogonal Projections
Recommended article: Reconstructing \(hv\)-convex polyominoes from orthogonal projections
Recommended article: Reconstructing convex polyominoes from horizontal and vertical projections
Recommended article: The number of convex polyominoes reconstructible from their orthogonal projections
Recommended article: Reconstruction of L-convex Polyominoes
Recommended article: Q4038559
description: scientific article; zbMATH DE number 7603275