18th IAPR International Conference on
Discrete Geometry for Computer Imagery

10-12 September 2014 Siena, Italy

Best paper award

The best paper award for the DGCI 2014 goes to

Non-additive bounded sets of uniqueness in Z^n
by Paolo Dulio, Sara Brunetti and Carla Peri.

Comments

This edition of DGCI has been characterized by a large number of interesting papers in the field of Discrete Tomography. Among them, this one concerns the uniqueness of the reconstruction process from a finite set of views for objects on a finite sized grid in 3 or more dimensions.

The paper is theoretically solid, and it brings light to a conjecture of Attila Kuba, reported by Peter Gritzmann et al. in 2011, by studying the existence and the number of 3D non-additive sets uniquely determined by projections.

The found results show both interesting theoretical developments, and practical consequences, as the reconstruction from sparse (minimal x-ray dose) additive sets becomes feasible, using linear programming methods, in polynomial time.

Paper abstract

A main problem in Discrete Tomography consists in looking for theoretical models which ensure uniqueness of reconstruction. To this, lattice sets of points, contained in a multidimensional grid A=[m_1]x[m_2]x...x[m_n] (where for an integer number p, [p]={0,1,...,p-1}), are investigated by means of X-rays in a given set S of lattice directions. Without introducing any noise effect, one aims in finding the minimal cardinality of S which guarantees solution to the uniqueness problem.

In a previous work the matter has been completely settled in dimension two, and later extended to higher dimension. It turns out that d+1 represents the minimal number of directions one needs in Z^n (n>=d>=3), under the requirement that such directions span a d-dimensional subspace of Z^n. Also, those sets of d+1 directions have been explicitly characterized.

However, in view of applications, it might be quite difficult to decide whether the uniqueness problem has a solution, when X-rays are taken in a set of more than three lattice directions. In order to get computational simpler approaches, some prior knowledge is usually required on the object to be reconstructed. A powerful information is provided by additivity, since additive sets are reconstructible in polynomial time by using linear programming.

In this paper we compute the proportion of non-additive sets of uniqueness with respect to additive sets in a given grid A of Z^n, in the important case when d coordinate directions are employed.