Polynomial Time Reconstruction of Regular Convex Lattice Sets from their Horizontal and Vertical X-Rays

We consider a problem of Discrete Tomography that has been open for 20 years: the reconstruction of convex lattice sets from their horizontal and vertical X-rays (X-rays is the mathematical term for the number of points of a set in a sequence of consecutive lines). We prove that it can be solved in polynomial time for the subclass of the regular lattice sets. Regularity is a property related to the relative position of the points of the set with extreme abscissa and ordinate. This algorithm that we call ConvexTomo follows the classical strategy initiated by E. Barcucci et al. for the reconstruction of horizontally and vertically convex 4-connected lattice sets. The approach introduced for the reconstruction of this class of lattice sets can be adapted until the creation of combinatorial structures called switching components. They are used to express horizontal and vertical convexity as a conjunction of 2-clauses. Then polynomial time algorithms solving 2-SAT provide polynomial time algorithms of reconstruction. The difficulty to overcome is that convexity (and no more directional convexities) requires 3-clauses which makes this approach no more polynomial. In this paper, we present a new approach encoding the research of a convex configuration of the switching components in the research of a path between two sets of vertices in a Directed Acyclic Graph. This reduction passes through the introduction of a new class of problems of computational and discrete geometry that we call Convex Aggregation: given a convex lattice set A ⊂ Z 2 and an ordered finite family of lattice sets B i ⊂ Z 2 called blocks (blocks are around A), does there exist a non empty subset of blocks such that their union with A remains convex? We reduce the question to the research of a path connecting two sets of vertices in a Directed Acyclic Graph. Then we investigate its variant related to the research of a convex configuration of the switching components. This problem is made of four related problems of Convex Aggregation. We reduce it again in a more complex manner to the research of a path in Discrete Acyclic Graph. It provides the final step of the algorithm ConvexTomo with a polynomial time complexity whereas the clauses approaches might be exponential. Fig. 1. Considered problem of Discrete Tomography: Find a convex polygon with given numbers of interior lattice points on the horizontal and vertical lines. The solution is a convex lattice set