Theoretical and algorithmic aspects of Discrete Geometry: inverse problems and tilings of the plane

This thesis covers four topics within the wide area of Discrete Mathematics: for each of them, we investigate a different open problem and contribute to its solution. Even if they could appear different at first glance, the leitmotif that connects all of them is the definition of inverse problems concerning discrete structures, represented as subsets of points of $\mathbb{Z}^{2}$ or as matrices having integer or binary entries. At first, we focus our attention on an inverse problem classically studied in the field of Discrete Tomography, that is, the reconstruction of an unknown (discrete) object starting from partial information on it. Usually, the interior of the object is supposed to be inaccessible, and the information is acquired by means of X-rays, mathematically modeled by discrete lines in $\mathbb{Z}^{2}$, and addressed as \emph{projections}, while the object to be reconstructed is modeled as a set of points of the discrete plane, or, equivalently, as a binary image that is represented through a binary matrix. The main drawback in the reconstruction process is that in most cases the acquired information is not sufficient for the faithful determination of the unknown image, meaning that, given a set of discrete directions in $\mathbb{Z}^{2}$, there exist in general different objects having the same projections along such directions, and so the reconstruction problem is ill-posed. The problem we consider in this thesis is the determination of sets of directions satisfying the uniqueness property, meaning that, when we collect the projections along the directions of such sets, a binary image can always be reconstructed with no ambiguities. We then move from the field of Discrete Tomography to the field of Graph Theory, where a similar inverse problem is defined: the reconstruction of a simple (hyper)graph starting from the knowledge of its degree sequence and of the cardinalities of its (hyper)edges. In the previous perspective, this is equivalent to the reconstruction of a binary matrix, specifically, the incidence matrix that is used to represent a hypergraph, starting from its horizontal and vertical projections, with the further constraint that all the rows of the matrix are required to be distinct. This last condition makes the reconstruction problem to be NP-hard, so that our research consists of the investigation of instances for which a solution can be easily and quickly detected. We also consider the inverse problem of reconstructing a generic set of points in $\mathbb{Z}^{2}$ using a generalized notion of projection introduced by Maurice Nivat: instead of considering discrete lines, so \emph{linear} projections, we collect the projections using bi-dimensional windows. In this sense, we fix a finite connected set of positions in $\mathbb{Z}^{2}$, called \emph{polyomino}, and we move it on the discrete plane taking note of the number of points that lie inside it, in order to detect the presence of the points of the set we want to reconstruct. In this case, a special role is played by exact polyominoes, i.e., those polyominoes that can be used to tile the discrete plane by translation. In the last part of the thesis, we move apart from inverse problems and we focus our attention on exact polyominoes. We consider a special class of them, called \emph{prime double squares}, and we carry on the study of a conjecture proposed by Blondin Massé et al. in~2013. We provide a solution for it, relying on tools from Combinatorics on words. We conclude by presenting some results that may constitute a step ahead the exhaustive generation and enumeration of the class of prime double square polyominoes.