{'fraction_non_alphanumeric': 0.038896490663232454, 'fraction_numerical': 0.009397134578235673, 'mean_word_length': 4.096605476361399, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
About the Reconstruction of Convex Lattice Sets from One or Two X-rays

We consider a class of problems of Discrete Tomography which has been deeply investigated in the past: the reconstruction of convex lattice sets from their horizontal and/or vertical X-rays, i.e. from the number of points in a sequence of consecutive horizontal and vertical lines. The reconstruction of the HV-convex polyominoes works usually in two steps, first the filling step consisting in filling operations, second the convex aggregation of the switching components. We prove three results about the convex aggregation step: (1) The convex aggregation step used for the reconstruction of HV-convex polyominoes does not always provide a solution. The example yielding to this result is called \textit{the bad guy} and disproves a conjecture of the domain. (2) The reconstruction of a digital convex lattice set from only one X-ray can be performed in polynomial time. We prove it by encoding the convex aggregation problem in a Directed Acyclic Graph. (3) With the same strategy, we prove that the reconstruction of fat digital convex sets from their horizontal and vertical X-rays can be solved in polynomial time. Fatness is a property of the digital convex sets regarding the relative position of the left, right, top and bottom points of the set. The complexity of the reconstruction of the lattice sets which are not fat remains an open question.


About Discrete Tomography
In the mid 1990s, researchers in Material Science and especially in three dimensional Electron Microscopy previewed the development of an upcoming technology able to count the number of atoms of a material crossed by a beam of straight lines Carazo et al. [1999]. Under the same principle than Computerized Tomography, they intended to use this process in order to reconstruct the 3D structure of different materials (proteins, crystals...) with a very high level of precision. In this new framework, the classical algorithms of Computerized Tomography have been unable to provide satisfying results. The CT algorithms have been designed for the investigation of materials at a scale where it can be assumed to be continuous. These algorithms are very poorly adapted for a level where the set of atoms is closer to a discrete set of points. The discrete nature of the objects to be reconstructed is the first difficulty which makes CT algorithms ineffective at the atomic scale. A second difficulty comes from the very low number of X-rays -from 2 to 10which can be used in Material Science since the X-rays damage the atomic structure (as comparison, CT-scans provide usually hundreds of X-rays). The third difference with Computerized Tomography is that for the reconstruction of the atomic structure of crystals (see Batenburg et al. [2009], Van Aert et al. [2011] for crystalline structures of nano-particules computed with Discrete Tomography in the 2010s years), the atoms are centered on a lattice so that the problem becomes the reconstruction of a lattice set, namely in dimension 2 a binary matrix.
The development of the technology for counting the number of atoms on straight lines took finally more time than expected but the impulse was given to explore this new range of questions dealing with the reconstruction of discrete sets of points. The sequence of the numbers of points of the intersections of a discrete set with consecutive parallel lines has been called by keeping the physical term of X-ray while the reconstruction of a discrete set from X-rays took the name of Discrete Tomography Gardner [1995], Herman and Kuba [1999,2007]. Due to the technical system providing the measurements and the complexity of the considered problems, a special attention is given on the problem in dimension 2.

Problem Statement
An X-ray is the sequence of the number of points of the intersection between a given lattice set and the consecutive diophantine lines in a chosen direction. In the particular case of the horizontal and vertical directions in dimension 2, we define the horizontal and vertical X-rays of a lattice set S ⊂ [0 · · · m − 1] × [0 · · · n − 1] as the two vectors H(S) and V (S) counting the numbers of points of S in each row and column. Their coordinates are h j (S) = |{(x, y) ∈ S|y = j}| for 0 ≤ j ≤ n − 1 and v i (S) = |{(x, y) ∈ S|x = i}| for 0 ≤ i ≤ m − 1 (Fig.1). Figure 1: The horizontal and vertical X-rays of the lattice set S are the vectors V (S) = (1, 2, 4, 5, 3, 1) and H(S) = (2, 4, 4, 5, 1).
It leads to introduce a generic problem of Discrete Tomography. The question is the existence of a lattice set with given X-rays and belonging to a given class A of lattice sets. We consider in this paper the problems of reconstruction from one or two X-rays. Problem 1 (DT A (v)). Given a class A of finite lattice sets, Input: one vector v ∈ Z m . Output: does there exist a lattice set S ∈ A included in the strip [0 · · · m − 1] × Z with V (S) = v ?
With a vertical and an horizontal X-ray instead of just a vertical X-ray, we have the following problem: Problem 2 (DT A (h, v)). Given a class A of finite lattice sets, Input: two vectors h ∈ Z n and v ∈ Z m . Output: does there exist a lattice set S ∈ A included in the rectangle [0 · · · m − 1] × [0 · · · n − 1] with V (S) = v and H(S) = h ?
The two problems DT A (v) and DT A (h, v) are highly dependant on the chosen class A. In the paper, we focus our attention on convex lattice sets but different definitions might be considered (Fig. 2). Definition 1. A lattice set S ⊂ Z 2 is a polyomino if it is 4-connected namely if any pair of points of S is connected by a sequence of points of S at Euclidean distance 1. The class of polyominoes of Z 2 is denoted P.
A lattice set S ⊂ Z 2 is horizontally (vertically) convex if its intersection with any horizontal (vertical) line is a set of consecutive points. The class of horizontally (vertically) convex lattice sets is denoted H (V for vertically convex sets). Horizontally and vertically convex sets are simply said HV-convex. Their class is H ∩ V.
A lattice set S ⊂ Z 2 is digital convex if it is equal to its intersection with its real convex hull S = conv Z 2 (S) where the operator conv Z 2 (.) denotes the integer convex hull namely conv R 2 (.) ∩ Z 2 . The class of the digital convex lattice sets is denoted C.
The class of HV-convex polyominoes is the intersection H ∩ V ∩ P . It is not convex in an ordinary meaning. The digital convex sets are the intersections of convex polygons with the lattice Z 2 . Notice that the digital convex lattice sets are obviously HV-convex (C ⊂ H ∩ V).

Figure 2:
Main classes of convex lattice sets. The set S 1 is not a polyomino since not connected. The set S 2 is not horizontally convex, S 3 is not vertically convex. The set S 4 is connected, horizontally and vertically convex. It is a HV-convex polyomino and then belongs to the class H ∩ V ∩ P. The set S 5 is not digital convex while S 6 is digital convex (S 6 ∈ C).

State of the Art
It is known for a long time that for the whole class denoted W of all lattice sets, the problem DT W (h, v) can be solved in polynomial time by specific algorithms Gale [1957], Ryser [1957] of by min cut-max flow algorithms (Fig. 3). Many variants of the problem DT W (h, v) have been investigated, not only with horizontal and vertical X-rays but in different dimensions, with different directions of X-rays and different kinds of atoms. If we focus on the two-dimensional case with horizontal and vertical X-rays, the complexities of the problem DT A (h, v) have already been determined for several classes A. The problem DT A (h, v) is NP-complete: • for the class A = P of polyominoes Woeginger [2001] • for the classes A = H or A = V of horizontally or vertically convex lattice sets Barcucci et al. [1996]. • for the class A = H ∩ V of HV-convex lattice sets (it is a particular case of puzzle games called nonograms) Woeginger [2001].
These N P -hardness results are however counter-balanced by two major results of the field published in two seminal papers: • The problem DT H∩V∩P (h, v) i.e the reconstruction of HV-convex polyominoes can be solved in polynomial time Barcucci et al. [1996]. • Results of uniqueness have been obtained for the class C of digital convex lattice sets with different number of directions of X-rays. R. Gardner and P. Gritzmann characterized the sets of d directions for which any digital convex lattice set is uniquely determined by its X-rays Gardner and Gritzmann [1997]. With the directions of X-rays providing uniqueness, these results have been completed by a polynomial time algorithm of reconstruction Brunetti and Daurat [2008a]. This algorithm follows the two steps used for the reconstruction of HV-convex polyominoes Barcucci et al. [1996].

Three Results
Our goal is to address the problem DT C (h, v). It is a twenty years old open question of Discrete Tomography , Marco and Frosini [2022]. Unfortunately, we solve it only partially by providing a polynomial time algorithm for a subclass of the digital convex sets C that we call fat. We present two intermediary results which have their own interest. Then the article contains three results.
1 -The bad guy. The first result is about the reconstruction DT H∩V∩P (h, v) of HV-convex polyminoes. It has been observed since many years that the second step of the original algorithm Barcucci et al. [1996] always provides a solution. It became an oral conjecture. We disprove it with a first counter-example. This counter-example has been called by Andrea Frosini the bad guy.
2 -Only One X-ray. The second result states the complexity of the problem of reconstruction of digital convex sets from only one X-ray: where m is the number of columns of the X-ray and m−1 i=0 v i the number of points to determine.
The result is interesting by itself but also by the strategy of the algorithm. It reduces the computation of a solution to the research of a path in Directed Acyclic Graph of polynomial size.
3 -With Two X-rays and a fatness property. The third result is about the reconstruction of digital convex lattice sets from horizontal and vertical X-rays namely DT C (h, v). We provide a polynomial time algorithm called DAGTomo2 for reconstructing the fat digital convex sets (Fig.5). The fatness of a digital convex set is related to the positions of its points with minimal and maximal x and y coordinates. These extreme points are the feet of the lattice set (Fig.4). Definition 2. Given a lattice set S ⊂ Z 2 , the South, West, North and East feet are The lattice set S is thin if there exists (X, Y ) ∈ Z 2 such that the feet are strictly located in diagonally opposite quadrants of (X, Y ) i.e verifying either x(South(S)) < X < x(North(S)) and y(West(S)) < Y < y(East(S)), or x(South(S)) > X > x(North(S)) and y(West(S)) > Y > y(East(S)). If S is not thin, it is fat (Fig.5). The time complexity of DAGTomo2 is high but polynomial. The complexity of the reconstruction of the thin digital convex sets DT C\F (h, v) remains an open question.

Plan
The paper is organized with one section per result. The second section is focused on the reconstruction of HV-convex sets. It presents the bad guy counter-example and introduces the material necessary to prove Theorem 2.
The third section proves Theorem 1 by presenting a polynomial time algorithm DAGTomo1 for solving DT C (v). The fourth section presents the polynomial time algorithm DAGTomo2 for solving DT C∩F (h, v). It proves Theorem 2.
2 The bad guy counter-example and how it has been built ?
This section is focused on the reconstruction of HV-convex polyominos. It summarizes the results of the two previous episodes Barcucci et al. [1996] and Gerard [2019] by defining the switching components and provides a counter-example of a conjecture.

Episode 1: the Reconstruction Procedure with its Filling/Aggregation Strategy
The milestone paper Barcucci et al. [1996] proved that the problem DT H∩V ∩P (h, v) can be solved in polynomial time. There exists an extensive literature around this problem Frosini [2022, 2021] and several algorithms have been derived from this algorithm , Brunetti and Daurat [2008a], Frosini and Vuillon [2019], Brunetti and Daurat [2008b]. We recall its two steps strategy and how it deals with the ambiguities of the reconstruction.
The strategy of the algorithm is to assume that some points of the solution are known and then to perform a reconstruction procedure. The given subset of a solution S is denoted Kernel 0 . The algorithm tries several subsets Kernel 0 and for each, the algorithm repeats the reconstruction procedure.
Choosing the feet. The first set of points Kernel 0 assumed to belong to the solution is not chosen randomly. The original strategy of Barcucci et al. [1996] is to choose as set Kernel 0 the four feet North, South, East, and West (Fig.4). The North and South feet might have at most m different positions while the East and West feet might have at most n different positions. It leads us to perform the reconstruction procedure for at most m 2 n 2 different initial kernels Kernel 0 (Fig.6). We present now the reconstruction procedure. It uses a partition of the grid in three sets presented in the following paragraph. The two steps of the reconstruction procedure i.e the filling and aggregation steps are presented in the later.
Kernel, excluded and undetermined points. During the reconstruction procedure, the current knowledge of the solution is described by a partition of the rectangular region of interest [0 · · · m − 1] × [0 · · · n − 1] in three sets denoted Kernel, Out, and Undetermined.
• The kernel Kernel contains the integer points which are currently known to belong to all solutions (up to the considered subset Kernel 0 ). • The set Out contains the integer points which are currently known to be excluded from all solutions. • The set of the integer points whose status In or Out of a solution has not yet been determined is denoted Undetermined. It is also often called the shell.
For each execution of the reconstruction procedure, the kernel Kernel, the set of the excluded points Out and the set Undetermined of the undetermined points are respectively initialized with Kernel ← Kernel 0 , Out ← ∅ and Filling step. Once the three sets Kernel, Out and Undetermined have been initialized, the prescribed X-rays and the prescribed properties of the solution (4-connectivity and HV-convexity) can be used to decrease the set of the undetermined points. Some of them are added to the current solution Kernel while some other points cannot belong to the solution and are added to Out. Then the new determined points allow us to determine new points. The algorithm repeats this process until no undetermined point could be determined. This step of the reconstruction procedure from the initialization to the stage where no undetermined point can be determined without ambiguity is called the filling step.
We refer to Brunetti et al. [2006], Brunetti and Daurat [2008a] for a complete presentation of the filling operations and suitable data structures. The filling operations run until either finding a contradiction (a point of Kernel that should be also assigned to Out or conversely) or until no undetermined point could be determined without ambiguity.
If the filling operations find a contradiction, there is no solution with the considered position of the feet. This branch of the computation is stopped. If there is no contradiction and it does not remain any undetermined point, then a unique solution has been found with the considered position of the feet. This branch of the computation also ends. We go to the aggregation step only if it remains undetermined points without contradiction.
The switching components. We place us now in the case where the filling step did not find any contradiction and where it remains some undetermined points. Then the kernel obtained by using the filling operations of Barcucci et al. [1996] has the properties to be HV -convex and 4-connected. The connectivity allows us to partition the undetermined points in four subsets that we call the borders: the North West, North East, South East and South West borders. They are respectively denoted NW, NE, SE and SW (Fig.6).
Then we have a partition of the undetermined points in Undetermined = NW ∪ NE ∩ SE ∩ SW. We can build another partition in the following way. The starting remark is that an undetermined point cannot be isolated in a row or a column. Otherwise it would have been determined. The undetermined points go by pair on each row and column. If for instance p = (i, j) is undetermined and belongs to the South border SW ∪ SE, then the point denoted p = (i, j + v i ) is a North undetermined point. These two points are vertical correspondents. In the same way, any West undetermined point |p = (i, j) has an horizontal East correspondent p| = (i + h j , j) (Fig.8). Horizontal and vertical correspondences are symmetric relations. Figure 8: Corresponding points and switching components. After the filling step, horizontal correspondences are drawn in blue while the vertical correspondences are drawn in green on the bad guy instance. In this case, the graph is composed of a unique cycle i.e switching component.
We present now the main property of corresponding points (Fig. 9). If no one of two corresponding points is aggregated to the kernel then the number of points on its row or column is too small. Conversely, if both points are aggregated to the kernel, there are too many points on the row or column. It follows that exactly one point per pair of corresponding points has to be aggregated to the kernel. We associate now to each undetermined point a Boolean variable assigned to 1 if we decide to aggregate the point to the kernel and to 0 if it is rejected. These variables are called the aggregation variables. It follows from the previous remark that the values of the aggregation variables of corresponding points are the negation from each other. We represent graphically this relation by denoting the points either with a square or with a diamond ♦.
If we consider now the graph of the corresponding points, each point is a vertex of degree 2. It follows that the graph of correspondences is an union of cycles each one called switching component.
Definition 3. A switching component P is a cycle of corresponding undetermined points (Fig.9). Aggregation step. It remains us to determine which undetermined points should to be aggregated the kernel or rejected. In other words, the problem is to find an assignation of the aggregation variables associated to the undetermined points which provides a set which is 4-connected, HV-convex and has the prescribed numbers of points in each row and column. The key point of the algorithm from Barcucci et al. [1996] is that these properties are easily expressed by a 2-CNF on the aggregation variables. Then finding an HV-convex polyomino with the prescribed horizontal and vertical X-rays is reduced to a 2-SAT instance. Then the aggregation step is resolved by computing and solving the 2-CNF in polynomial time Aspvall et al. [1979].
Old oral conjecture. 25 years after the seminal paper presenting this algorithm Barcucci et al. [1996], no instance was found where the 2-SAT CNF on the aggregation variables was not feasible. This observation led to the following empirical conjecture: the 2-SAT formulas expressing the HV-convexity of a solution on the aggregation variables always feasible.
To determine whether this conjecture is true or false and also for the reminder of the paper, we now present some structural properties of the switching components.

Episode 2: Structures of the Switching Components
Before going further, notice that the properties used for the reconstruction procedure of an HV-convex solutions can also be used for the reconstruction of digital convex lattice sets since digital convexity implies HV-convexity.
According to Gerard [2019], the structures of the switching components can be classified according to the positions of the feet. There are six different configurations presented in Fig. 10. In the configurations a), b), c), d), e), the positions of the feet provide thin solutions while the configuration f) is the configuration of the fat convex lattice sets.
For each one of the six configurations, the set of undetermined points is restricted to a small number of regions. Each region corresponds horizontally and vertically to some other regions, so that we can build the graph of the vertical and horizontal correspondences of the regions. The correspondence graph in the configuration c) is for instance represented in Fig. 11. Such graphs admit a small number of fundamental cycles i.e minimal closed paths. There are exactly three minimal cycles in the configuration c). The closed path in the graph are obtained by concatenation of these minimal cycles. The fundamental minimal cycles in all configurations are represented in Fig. 12. They provide a better understanding of the very constrained structures of the switching components.  Gerard [2019]. We color in black the feet and the points that can be directly determined because they are in the same rows or columns. We color in red some of the points which can be directly excluded and in grey the regions of the undetermined points. Figure 11: In the configuration c) the graph of correspondences between the undetermined regions. We consider the graph of vertical and horizontal correspondences of the different regions that might contain undetermined points (with different colors). Each region appears twice in the graph, once after an horizontal correspondence and the other after a vertical correspondence. This graph admits six fundamental oriented cycles and three without orientation. With feet in configuration c), the switching components are necessarily concatenations of these three fundamental cycles.

The Bad Guy
Let us come back to the conjecture that the aggregation 2-SAT formula expressing the HV-convexity of a solution is always feasible. For the configurations b), d), and f), it is true: a solution can be found by aggregating to the kernel either all the squares or all the diamonds. For having a chance to provide an example of a non feasible aggregation formula, we need squares and diamonds in the same region as in the following counter-example.
The bad guy instance is in configuration c) and we have a unique switching component which is a concatenation of a fundamental cycle c2) and a fundamental cycle c3) (these two cycles are drawn in Fig. 12). The filling step is illustrated in Fig.7. The correspondences are illustrated in Fig.8 and the Boolean aggregation variables are represented in Fig.13. The 2-SAT formula expressing the HV-convexity of a solution admits no solution since a square implies a diamond, which is contradictory. It disproves the empirical conjecture. There exists reconstruction instances for which the aggregation 2-SAT CNF is not feasible. Figure 12: The fundamental cycles of the switching components in each configuration (except the configuration a) for which the path can have an arbitrary number of edges in the central region). Notice that the cycle c3) has been forgotten in Gerard [2019]. The list is now complete. Figure 13: Counter-example of the conjecture. The filling operations lead to a unique switching component. It was conjectured that when the filling operations do not lead to an inconsistency, there exists always an assignment of the switching components providing an HV-convex solution. It is false with this example. The HV-convexity leads to inconsistent 2-clauses.

Work in a Bounded Region
We assume without loss of generality that the first and last coordinates of the input vector v are not null. It guarantees that any solution S of DT C (v) contains points in the vertical lines x = 0 and x = m − 1.
The lowest points of a solution S on these two lines are respectively called the left and right bottom points. Then instead of searching an arbitrary solution of DT A (v), we are going to restrict our research to a solution where the left and right bottom points belong to a bounded region.
The first remark is that vertical translations preserve the vertical X-ray and the digital convexity. Then the set of the  We bound now the region of the other points of a solution. We consider the column x = i. The coordinate of the vertical X-ray along the line x = i is v i . We notice that if a point (i, y) belongs to a solution of DT A (v), then its vertical distance to the triangle T m is at most v i . Otherwise the solution would not be convex. The region whose points (i, y) are at vertical distance at most v i from T is denoted R v . It contains at most m(m+1) i=0 v i is the prescribed number of points of any solution. We have shown that if DT A (v) admits a solution, then there exists a solution included in R v . The algorithm DAGTomo1 searches for a solution in this region.

DAGTomo1
We present now the algorithm DAGtomo1 which solves DT C (v) by searching for a solution in the region R v . The strategy is to reduce the problem to the search of a path in a directed acyclic graph (DAG).
The DAG. We consider the following Directed Acyclic Graph Γ(v) whose nodes are convex quads with the prescribed vertical X-ray and linked by edges if they have a convex junction (Fig.15). To be more precise, • the nodes of Γ(v) are quads made by a pair of non vertical segments s, s in the following configuration.
1. First, the four vertices of the two segments s and s are in convex position (one vertex can be in common if it is the origin or if its x coordinate is m − 1) and belong to R. 2. We denote [a · · · b] the interval of the common x-coordinates of the two segments s, s. We assume that the integral interval [a..b] is not empty. Otherwise, the pair of segments s, s is excluded from the nodes. 3. The last condition is that the segment s is above the segment s with the prescribed X-ray. Figure 15: Quads. The nodes of the DAG are quads (colored in pink). The common columns of s and s are highlighted in blue. For each one of these columns, the number of points of the quad is equal to the prescribed value given by the vertical X-ray.
• We consider two nodes s 1 , s 1 and s 2 , s 2 . We denote [a 1 ..b 1 ] (respectively [a 2 ..b 2 ]) the interval of the common x coordinates for the two pairs of segments s 1 , s 1 (respectively s 2 , s 2 ). The DAG Γ(v) has an oriented edge from s 1 , s 1 to s 2 , s 2 if 1. they have a common segment: either s 1 = s 2 or s 1 = s 2 , 2. the two segments s 1 and s 2 which are not equal are consecutive: the right vertex x of s 1 is equal to the left vertex of s 2 . 3. moreover, the two different segments are in a convex configuration: the vertex x is not in the convex hull of the other vertices.
We introduce now two sets of nodes called Left and Right containing respectively the left-most and right-most quads.  Reduction. We reduce the reconstruction DT C (v) of a digital convex set of vertical X-ray v to the research of path going from Left to Right in the DAG Γ(v) (Fig.17).

Proposition 1. The problem DT C (v) admits a solution if and only if there exists a path going from Left to Right in the DAG Γ(v).
Proof. By construction, if there exists a path in the DAG Γ(v), we consider the solution S obtained by union of its quads. The constraints on the quads to be a node guarantee the prescribed X-ray while the constraint on the direction of the turn at each edge guarantee the convexity of S. Thus a path from Left to Right provides a solution of DT C (v).
Conversely, if we have a solution S of DT C (v), its convex hull is fully covered by a sequence of consecutive quads. It provides a path from Left to Right. It can be noticed that if one of the quads has a vertical edge, the path is not unique since we can advance either on the upper side or on the lower side of the convex hull of S.
Algorithm. The algorithm DAGTomo1 builds a part of the DAG Γ(v) and searches for a path from Left to Right.
The graph Γ(v) contains at most k 4 nodes/quads where k is cardinality of the region R. Each node has at most 2k edges since one of the left nodes is replaced by another point of R. There is no interest in computing the whole graph Γ(v) since we search for a path issued from Left. The algorithm DAGTomo1 computes the nodes reached from Left. The main loop of the algorithm is the following: given a node/quad q, we consider the at most 2k quadrilaterals that can be consecutive neighbors of q. We test whether the new quadrilateral has already been reached in a sorted list of all the quadrilateral which have already been considered. This test takes O(log(k 4 )) time. If it is the first time that we meet it, we test whether its X-ray is equal to the prescribed X-ray for the common columns of the two segments. Computing the X-ray of a quad takes at most O(m) time. If the X-ray is valid, we test the convexity of the turn in constant time and store q as antecedent. At last, we test whether this quadrilateral belongs to Right in constant time.
The algorithm DAGTomo1 ends either when a path reaching Right is found or when all the nodes reached by starting from Left have been explored. Its worst-case time complexity is O(k 4 (m + log(k))). In order to provide a simple bound, we use m + log(k) ≤ mk. It provides a worst-case time complexity in O(mk 5 ). We have already bounded k by m(m+1) With the inequality (a + b) n ≤ (2a) n + (2b) n = 2 n (a n + b n ) for positive a and b, the property that and proves Theorem 1.

Reconstructing Fat Digital Convex Sets in Polynomial Time
In this section, we present the algorithm DAGTomo2 for reconstructing fat digital convex sets from their horizontal and vertical X-rays. The property that this algorithm runs in polynomial time proves Theorem 2. The algorithm DAGTomo2 uses a two-step reconstruction procedure as presented for reconstructing HV-convex polyominoes with first the filling step and secondly the aggregation step. We update the filling step for taking into account the digital convexity which replaces the connectivity and the HV-convexity. The updated filling operations are presented in Section 4.2. The aggregation step used for HV-convex polyominoes is completely modified by using a DAG strategy as in Section 3. This main new step is presented in section 4.3.

Initialization
As the classical algorithm reconstructing HV-convex polyominoes and described in Section 2, the algorithm DAGTomo2 works with a partition of the grid in three sets of points [0 · · · m − 1] × [0 · · · n − 1] = Kernel ∪ Out ∪ Undetermined. The kernel is initialized by choosing a position of the feet: Kernel ← South ∪ West ∪ 'North ∪ East. Notice that we do not only compute the kernel Kernel but we will also maintain at each step its convex hull. For each position of the feet, we proceed to the DAGTomo2 reconstruction procedure. This reconstruction procedure has two steps, first the filling step and secondly the aggregation step.

Filling Step
We precise now the filling operations of the reconstruction procedure. Some of the filling operations are different from the ones used for reconstructing HV-convex polyominoes because we no more assume the 4-connectivity of the solution.
New Convex Filling Operations. As we search for a digital convex solution, the first filling operation is Kernel ← conv Z 2 (Kernel) where conv Z 2 denotes the operator providing the set of the integer points in the continuous convex hull of the set. By definition, a set S is digital convex if and only if we have conv Z 2 (S) = S. As the convex hull of the kernel contains the feet, it provides directly a partition of the undetermined points in four borders NW, NE, SE and SW (see Fig.18). While this partition requires to use the connectivity and complex filling operations for reconstructing HV-convex polyominoes, it is direct for digital convex sets. The initial computation of the four sets NW, NE, SE and SW takes O(mn) operations.
Each time that a new point is added to the kernel, we update the kernel with Kernel ← conv Z 2 (Kernel) to maintain a convex solution. The number of nodes is bounded by 2(m + n). Computing the new convex hull takes at most O(log(m + n)) (it is an insertion in the list of the nodes) and adding the lattice points in conv Z 2 (Kernel) takes again O(log(m + n)) per point namely a total time of O(mn log(m + n)) (more efficient data structures can be found in Figure 18: Initialization of Kernel, Out, NW, NE, SE and SW for two different instances. On the left, the different possible positions of the feet. A position of the feet being chosen (in black), the other points with x = 0 or x = m − 1 or y = 0 or y = n − 1 are added to Out (in red). The undetermined points are colored in grey. On the right, we proceed to the filling operation Kernel ← conv Z 2 (Kernel). It provides directly a partition of the undetermined points in four subsets NW, NE, SE and SW. Brodal and Jacob [2002]). By repeating this operation at most mn time, the total time taken by this filling operation is bounded by O(m 2 n 2 log(m + n)).
Each time that a new point x is added to the set Out of the excluded points, we test whether there exist undetermined points y such that x is in the convex hull of the union {y} ∩ Out. If x is in {y} ∩ Out, then y is excluded and added to Out. For each point x and each suspected point y ∈ Undetermined, the computation of the convex hull of {y} ∩ Out takes at most O(log(m + n)) time. Testing whether x is in this convex hull takes a constant time by just testing whether x is in the triangle of vertices y and the two adjacent vertices in the convex hull. Repeating this process for at most mn points x takes O(m 2 n 2 log(m + n)) time.
Regular Filling Operations. We describe the classical filling operations on a row but similar filling operations are executed on the columns. The row y = j is decomposed into five horizontal segments with their x-coordinates in the intervals [0 · · · a], ]a · · · b[, [b · · · c], ]c · · · d[ and [d · · · m − 1] (some of them can be empty). The two segments with points of x-coordinates in [0 · · · a] and [d · · · m − 1] contain the left and right excluded points. The central segment [b · · · c] contains the kernel points while the two intermediate intervals ]a · · · b[ and ]c · · · d[ are the x coordinates of the undetermined points.
Then the regular filling operations are done by updating the values of a, b, c and d in the following way : These four filling operations reduce the set of the undetermined points.
End of the filling step. The filling step ends in three cases: 1. A contradiction is found by adding an excluded point to the kernel or conversely by adding a kernel point to the excluded points. Then the reconstruction procedure fails. It shows that the considered position of the feet does not provide any solution.
2. The set of the undetermined points becomes empty. Then for the considered position of the feet, a unique solution has been found and the reconstruction procedure ends with a unique solution.
3. No new undetermined point can be determined. It is the unique case where the reconstruction procedure requires to proceed to the aggregation step.

Aggregation step
We proceed to the aggregation step in the case where it remains undetermined points after the filling step. The aggregation step for the HV-convex polyominoes uses the switching components. The aggregation step of DAGTomo2 does not use it. It uses the same strategy as the aggregation step of DAGTomo1 by reducing the computation of a solution to the research of path in Directed Acyclic Graph.
The four undetermined borders. The goal of the convex aggregation is to finalize the computation of a solution of DT C∩F (h, v). This solution can be described by the convex polygonal lines joining the West and East feet to the South and North feet. The vertices of the polygonal line going from the West to the North feet might either be some vertices of the convex hull of the kernel or some undetermined points in the NW border. This set of potential vertices is denoted NW with NW = NW ∩ NWV where NWV is the set of the north west vertices of the convex hull of the kernel i.e the vertices between the North and the West feet. The set NWV and thus also NW contain the upper point of the West foot and the leftmost point of the North foot. Figure 19: The four borders. After the filling step, the convex hull of the kernel is colored in yellow. The set of the potential vertices NE , NW , SE and SW contain the undetermined points of each border and the vertices of the convex hull of the kernel (the example shown above is not realistic since the filling operations would complete the kernel but this non-realistic example provides a better understanding of these sets). The points of these four sets are represented by blue, orange, pink and green dots. Notice that two sets of potential vertices share a point when a feet contains a unique point.
We define in the same manner the set of the potential vertices for the North East, South West and South East borders as NE = NE ∩ NEV, SW = SW ∩ SWV, and SE = SE ∩ SEV where NEV, SWV and SEV are the vertices of the convex hull of the kernel on each border. Each set of potential vertices contains the extreme points of the feet (Fig.19).
The central fully determined strips. We consider here the reconstruction of fat digital convex sets. It requires that the feet are in relative positions leading to a fat solution. In this case, the four undetermined borders are in a special configuration. According to the analysis of the configurations of the switching components presented in figure 10Gerard [2019], the borders containing the undetermined points are restricted to only four regions corresponding vertically and horizontally as drawn in Fig.20. We denote Hstrip the horizontal central strip containing the West and East feet and whose points are fully determined. The points in this strip belong either to the kernel or have been excluded but no one is undetermined. In the same way, we denote Vstrip the central vertical strip containing the South and North feet and whose points are fully determined. These two strips define a cross and the four undetermined borders are around it. The DAG. We introduce the Directed Acyclic Graph Γ(h, v) built from the h and v X-rays and from the four sets of potential vertices NW , NE , SW , and SE as follows.
• The nodes of Γ(h, v) are octagons defined with four (non degenerated) segments s NW , s NE , s SW , s SE satisfying some constraints (Fig.22). The role of each segment s NW , s NE , s SW , s SE is to become an edge of the final solution. The octagons q = s NW , s NE , s SW , s SE that we describe here with their segments and constraints are the central piece of the algorithm DAGTomo2.
1. The vertices of the segments s NW , s NE , s SW , s SE belong respectively to the sets of potential vertices NW , NE , SW , SW that we introduced in the previous paragraphs. 2. The support line of each segment s must be on one side of the kernel and not separate it into two parts.
Otherwise, the segment s can not be an edge of a convex set containing the kernel. 3. The octagon (here the convex hull of the four segments) does not contain any excluded point. 4. The next condition is the condition which guarantees that the X-ray of the solution fits with the prescribed X-rays h and v. We first associate to each segment s NW , s NE , s SW , s SE the set of consecutive rows and columns that it involves. For a segment s, these two sets are denoted rows(s) and columns(s). The sets rows(s) and columns(s) first contain the consecutive integer rows and columns crossed by s (Fig.21). If the segment s NW = xy has one vertex x in the horizontal strip Hstrip, then we can extend the known polygonal line until the West foot since this left upper hull of the solution is already known until the West foot. It leads us to complete columns(s NW ) with its left columns. We proceed in the same way with the vertical strip. If the segment s NW = xy has one vertex y in the vertical strip Vstrip, then we complete rows(s NW ) with the rows above it. By symmetry and rotations, we extend in the same manner the six other sets rows(s NE ), columns(s NE ), rows(s SE ), columns(s SE ), rows(s SW ), columns(s SW ).

Figure 21
: Some segments and their associated rows and columns. In image 1, we see the NW border with potential vertices in orange and the horizontal and vertical fully determined strips Hstrip and Vstrip colored in grey. In image 2, the segments a, b, and c are not valid because the support lines of a and c separate the kernel while b includes an excluded point. In image 3, we have three valid segments s NW . In the images 4, 5, 6 the rows of rows(d), rows(e) and rows(f ) and the columns of columns(d), columns(e) and columns(f ) are colored in blue. Notice that since d has a vertex in the horizontal strip Hstrip, its set of columns is extended until the West foot.
Once the rows and columns associated to each segment are define, we can go to the octagon. Each octagon is determined by its four segments s NW , s NE , s SW , s SE whose role is to become four edges of the convex hull of a solution. Then the octagon q fully characterizes the points of the solution in the rows in N orthRows(q) = rows(s NW ) ∩ rows(s NE ) and SouthRows(q) = rows(s SW ) ∩ rows(s SE ) and in the columns in W estColumn(q) = columns(s NW ) ∩ columns(s SW ), and RightColumn(q) = columns(s NE ) ∩ columns(s SE ) (these rows and columns are colored in blue in Fig.22). Now we give a condition on the octagon q to be a node: the four sets of rows N orthRows(q), SouthRows(q) and columns W estColumn(q), RightColumn(q) must be none empty and for each of these rows and columns, the number of integer points between each pair of segments must be equal to the prescribed coordinate of the input X-ray.

Figure 22:
An octagon/node of Γ(h, v). The octagon q is defined by its four non degenerated segments s NW , s NE , s SW , s SE whose vertices are chosen respectively in NW , NE , SW and SE (the orange/blue/green/pink dots). The main conditions for the octagon q =to be a node are that the rows N orthRows(q), SouthRows(q) and the columns W estColumn(q), RightColumn(q) are non empty and that for each one of the rows and columns in these sets, the number of integer points between the segments fits with the prescribed coordinates of the X-rays. On this example, it can be noticed that columns columns(s NE ) of the NE edge is not restricted to the columns crossed by the segment. They go until the West foot because both right vertices of s NE and s SE are in the horizontal strip Hstrip (colored in grey).
• We consider two nodes. There is an edge from the node q to the node q if they have three common segments and the two segments which differ define a convex turn. To be more precise, they must satisfy the following conditions: -The two nodes q and q have three segments in common. Let us assume for instance that we have the two nodes q = s NW , s NE , s SW , s SE and q = s NW , s NE , s SW , s SE . The three segments s NE , s SW , s SE are in common and the two segments s NW and s NW are different. -The two different segments s NW and s NW are consecutive (the right vertex of s NW is the left vertex of s NW ). -The turn at the common vertex is convex (in the sens that the union of the convex hulls of the two octagons q = s NW , s NE , s SW , s SE and q = s NW , s NE , s SW , s SE is convex).
Start and End nodes. We introduce now two special sets of octagons Start and End (Fig.23).
• Start is the set of nodes/octagons with the property that the four segments s NW , s NE , s SW and s SE have one vertex in the horizontal strip Hstrip and the other vertex outside. • End is the set of nodes/octagons such that the four segments s NW , s NE , s SW and s SE have one vertex in the vertical strip Vstrip and the other vertex outside.
Notice the special configurations of the rows N orthRows(q), SouthRows(q) and columns W estColumn(q), RightColumn(q) for octagons in Start and End. For an octagon in Start, the determined rows and columns do a H while for the an octagon, they do an I (with large bars below and above the vertical segment). If we now consider a continuous transformation of an octagon q going from Start to End, its rows N orthRows(q), SouthRows(q) and columns W estColumn(q), RightColumn(q) sweep the whole intermediate rows and columns. It is the strategy followed by the algorithm DAGTomo2 in order to guarantee that the X-rays of a solution correspond to the prescribed X-rays.
Reduction. We reduce the problem of convex aggregation for solving DT C∩F (h, v) to the research of a path going from Start to End in the graph Γ(h, v). Proof. We prove the proposition 2 by showing first that if DT C∩F (h, v) admits a solution, then there is a path from Start to End in the graph Γ(h, v) and secondly by stating that the existence of a path from Start to End provides a solution of DT C∩F (h, v).
We first assume first that DT C∩F (h, v) admits a solution S with the considered position of the feet. The filling step provides the set of the undetermined points. According to Gerard [2019], the undetermined points are organized in four borders NW, NE, SE and SW separated by a vertical strip Vstrip and a horizontal strip Hstrip of fully determined rows and columns. Then the undetermined part of the solution S can be decomposed in a sequence of octagons q i for 0 ≤ i ≤ k as drawn in Fig.24. Different sequences of consecutive octagons can be obtained. It depends on the order chosen to move the segments. Each one provides a path from Start to End.
Conversely, we assume that we have a path of consecutive octagons (q i ) 1≤i≤k in Γ(h, v) with its extreme octagons q 0 in Start and q k in End. We define the set O as the union of two sets. The first one contains the integer points in the octagons of the path. The second one is the kernel. Then we have O = 0≤i≤k q i ∩ Kernel. We now show that O is digital convex and has the prescribed X-rays.
The kernel is digital convex since one of the filling operations is Kernel ← conv Z 2 (Kernel). The set 0≤i≤k q i is also digital convex. It follows from the condition of having a convex turn between consecutive octagons in the graph Γ(h, v). We notice also that except in the horizontal and vertical strips Hstrip and Vstrip, the convex hull of the kernel is included in the union of the octagons 0≤i≤k q i . In other words, the union of the octagons is a convex layer around the kernel outside from Hstrip and Vstrip.
The unique points where we could have a non convexity are the vertices of the convex hull of the kernel where the octagons q 0 and q k are branched. The condition that the support lines of the segments of q 0 and q k do not separate the kernel guarantees that the junction is convex. Then the set O is digital convex.
We prove now that the horizontal and vertical X-rays of O are equal to the prescribed X-rays h and v. It is straightforward for the rows and columns of the two central strips Hstrip and Vstrip since there is no undetermined point in this region. For the remaining rows and columns, each octagon q i guarantees the X-rays for the rows N orthRows(q i ), SouthRows(q i ) and columns W estColumn(q i ), RightColumn(q i ). It remains to notice that by going from q 0 to q k , these guaranteed rows and columns cover all the raws and columns which are not in the already determined strips Hstrip and Vstrip.
DAGTomo2 aggregation algorithm. The DAGTomo2 aggregation algorithm is based on proposition 2 reducing the aggregation problem to the research of a path from Start to End in the graph Γ(h, v). The strategy is simple: 1. Compute the octagons in Start.
2. Compute the octagons which can be reached from Start with a Depth first search (each time that a new octagon is reached, the algorithm records its previous neighbor so that at the end we can backtrack the path).
The algorithm admits two variants which depend on which part of the graph Γ(h, v) is precomputed and stored. In any case, the algorithm requires to store a set of octagons reached from Start. The size of this set is O(m 4 n 4 ). In the variant that we consider, the vertices of the graph Γ(h, v) are precomputed but not the edges. The relations between the vertices are computed on the fly. The precomputation of the vertices of Γ(h, v) is done by considering all the potential octagons. We have O(m 4 n 4 ) quadruplets of segments s NW , s NE , s SE , s SW . Testing whether a quadruplet of segments defines a valid octagon requires to test two criterion: 1. Test whether the segments do not include an excluded point. It takes O(m + n) time by considering only the extreme excluded points.
2. Compare the X-rays of the octagon for the rows and columns that it fully determines with the input X-rays h and v. This comparison takes O(m + n).
Then the construction of the set of vertices of Γ(h, v) takes O((m + n)m 4 n 4 ).
Given an octagon q, the computation of its neighbors q is done on the fly in the following way: The neighbors of an octagon are obtained by moving only one of its vertices. The number of new vertices is O(mn). It makes O(mn) potential neighbors q for which we test the convexity of the union q ∩ q and whether q is a vertex of Γ(h, v). It takes a constant time.

Analysis
We now analyze the worst-case time complexity of the algorithm DAGTomo2. The number of feet positions being bounded by O(m 2 n 2 ), the algorithm executes at most O(m 2 n 2 ) reconstruction procedures.