Discrete tomography of model sets: Reconstruction and uniqueness

In this chapter, we study the discrete inverse problem of reconstructing finite subsets of in Euclidean d-space from their k-dimensional discrete X-rays with respect to finitely many linear subspaces. We are particularly interested in the computational complexities of the related algorithmic problems and in conditions that guarantee uniqueness of the data. These questions have been studied thoroughly for lattices. Here, our focus lies on extensions to Euclidean model sets or quasicrystals. Introduction Discrete tomography (DT) is concerned with the inverse problem of retrieving information about some finitely representable object in the Euclidean vector space from information about its intersections with certain query sets. Of particular interest is the problem of reconstructing some (or all) finite point sets F from given X-rays (F) parallel to a small number m of k-dimensional subspaces. More precisely, an X-ray of F is the sum function parallel to the subspace, which means that it gives the number of points of F on each k-dimensional affine space T parallel to. As will become obvious from our explanations below, the special case k = 1 of line X-rays is of great importance in practical applications; see Figure 2.1.1 for an illustration. A general problem of great interest is that of uniqueness: Does the given X-ray information suffice to determine the set F uniquely? One motivation for studying problems in DT comes from the requirement in materials science for the reconstruction, at the atomic level, of solid state materials from their images under quantitative high resolution transmission electron microscopy (HRTEM). In fact, in [41, 49], a technique is described which can, for certain crystals, effectively measure the number of atoms lying along densely occupied columns. Apparently, for these and many other practical purposes, the basic forms of the DT-problems outlined above have to be adapted to be able to cope with noisy measurements. While the best-studied case is that of subsets of a lattice L, there is growing interest in the determination of finite subsets of a fixed (and sufficiently nice) Delone set that is accessible only through X-rays in a given number m of lines spanned by interpoint (or difference) vectors of, the so-called lines.