Yan Gérard Limos
email: yan.gerard@uca.fr

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.

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 [START_REF] Carazo | Discrete Tomography in Electron Microscopy[END_REF]. 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. They started to use the algorithms of Computerized Tomography well-known in Medical Imaging. They discovered that these algorithms designed for the investigation of materials at a scale where it can be assumed to be continuous were absolutely not well-suited at 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 10-which 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 [START_REF] Batenburg | 3d imaging of nanomaterials by discrete tomography[END_REF][START_REF] Van Aert | Three-dimensional atomic imaging of crystalline nanoparticles[END_REF] 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 cardinalities 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 [START_REF] Gardner | Geometric Tomography. Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Herman | Discrete Tomography -Foundations, Algorithms and Applications[END_REF][START_REF] Herman | Advances in Discrete Tomography and Its Applications[END_REF]. Due to the technical principle providing the measurements and the complexity of the considered problems, a special attention has been given on the problem in dimension 2.

Problem Statement

An X-ray is the sequence of the cardinalities of the intersection between a given lattice set and the consecutive diophantine lines in a chosen direction. In the two-dimensional case of the vertical and horizontal directions, it leads to the following definition: .n], its vertical Xray V (S) ⊂ Z m is the vector of coordinates v i (S) = |{(x, y) ∈ S|x = i}| for 1 ≤ i ≤ m and its horizontal X-ray H(S) ⊂ Z n is the vector of coordinates h j (S) = |{(x, y) ∈ S|y = j}| for 1 ≤ j ≤ n (Fig. 2). 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:

Problem 1 (DT A (h, v)).
Given a class A of finite lattice sets, Input: two vectors v ∈ Z m and h ∈ Z n .

Output: does there exist a lattice set S ∈ A included in the rectangle [1..m] × [1..n] with V (S) = v and H(S) = h ?

The class A is a parameter of Problem DT A (h, v). We introduce the class C of convex lattice sets. Definition 2. A lattice set S ⊂ Z d is convex if it is equal to its intersection with its real convex hull S = conv R d (S) ∩ Z d (Fig. 3). The class of the convex lattice sets is denoted C. In other words, the convex lattice sets are the intersections of convex polygons with the lattice Z 2 . The complexity of their reconstruction DT C (h, v) is a twenty years old open question (Fig. 1). The purpose of the paper is to break the status quo and provide a partial answer opening new perspectives.

State of the Art

While Computerized Tomography has been stated on the prior works of J. [START_REF] Radon | Uber die bestimmung von funktionen durch ihre integralwerte langs gewisser mannigfaltigkeiten[END_REF] [START_REF] Radon | Uber die bestimmung von funktionen durch ihre integralwerte langs gewisser mannigfaltigkeiten[END_REF] or Fourier Analysis [START_REF] Bracewell | Strip integration in radio astronomy[END_REF], Discrete Tomography found its basis in results of D. Gale and H.J. [START_REF] Ryser | Combinatorial properties of matrices of zeros and ones[END_REF] [START_REF] Gale | A theorem on flows in networks[END_REF][START_REF] Ryser | Combinatorial properties of matrices of zeros and ones[END_REF] or in the more general theory of flows in networks by L.R. Ford and D.R. Fulkerson (1956) [START_REF] Ford | Maximal flow through a networks[END_REF].

According to these fundamental results, if we consider the whole class denote W of all lattice sets, the problem DT W (h, v) can be solved in polynomial time [START_REF] Gale | A theorem on flows in networks[END_REF][START_REF] Ryser | Combinatorial properties of matrices of zeros and ones[END_REF]. Another way to consider the problem is on a set of edges of a complete bipartite graph. It can be solved by any max-flow algorithm (Fig. 4). Many variants of this problem 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. In dimension 3, the problem is related with timetables or data security. Both variants are NP-complete [START_REF] Even | On the complexity of time table and multicommodity flow problems[END_REF][START_REF] Irving | Three-dimensional statistical data security problems[END_REF] and this extension is related with multi-commodity flow problems [START_REF] Gérard | About the complexity of timetables and 3-dimensional discrete tomography: A short proof of np-hardness[END_REF]. The reconstruction of sets with different kinds of atoms can also be considered with one X-ray per type of material. The problem becomes again NP-hard from two different kinds of atoms [START_REF] Gardner | On the computational complexity of determining polyatomic structures by x-rays[END_REF][START_REF] Dürr | Reconstructing 3-colored grids from horizontal and vertical projections is np-hard[END_REF]. Still in dimension 2, the number of X-rays can be increased with a result of NP-completeness from three X-rays [START_REF] Gardner | On the computational complexity of reconstructing lattice sets from their x-rays[END_REF].

In the two-dimensional case with horizontal and vertical X-rays, the complexities of the problem DT A (h, v) have already been determined for many classes A. The problem is NP-complete for the class of the 4connected lattice set (4-connected finite subsets of Z 2 are called polyomi-noes and their class is denoted P). We have also results with directional convexities. By denoting H the class of horizontally convex (H-convex) lattice sets i.e with consectutive points in any row (Fig. ??), the problem is NP-complete [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF]. We have of course the same result for the class denoted V of the vertically convex (V-convex) lattice sets. If we consider the class of the horizontally and vertically convex (HV-convex) lattice sets H ∩ V, the problem remains again NP-complete [START_REF] Woeginger | The reconstruction of polyominoes from their orthogonal projections[END_REF] (Fig. ??). Notice that the reconstruction of HV-convex lattice sets is a particular case of puzzle games called nonograms. In summary, while the initial problem DT W (h, v) without complementary constraints on the solutions can be solved in polynomial time, all the variants DT A (h, v) with P, H, V, H ∩ V as class A are NP-complete. These complexities in N P are however counter-balanced by two major results of the field published in two seminal papers [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF][START_REF] Gardner | Determination of finite sets by x-rays[END_REF].

-Horizontaly and vertically 4-connected subsets of Z 2 can be reconstructed in polynomial time:

DT A (h, v) is polynomial for the class A = H ∩ V ∩ P [2].
-On the other side, results of uniqueness have been obtained for the class C of 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 convex lattice set is uniquely determined by its X-rays [START_REF] Gardner | Determination of finite sets by x-rays[END_REF]. For n = 2 or n = 3 directions, for any directions, there exist ambiguous pairs or triplet of X-rays. For n ≥ 7 directions, all convex lattice sets are uniquely determined by their X-rays. For 3 < n < 7, the so-called cross-ratios of the directions provide a characterization of the sets of direction providing uniqueness or ambiguous X-rays [START_REF] Gardner | Determination of finite sets by x-rays[END_REF]. With the directions of X-rays providing uniqueness, these results have been completed by a polynomial time algorithm of reconstruction [START_REF] Brunetti | Reconstruction of convex lattice sets from tomographic projections in quartic time[END_REF]. This algorithm follows the same principle than the one used for the reconstruction of HV-convex polyominoes [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF].

Class A H and V X-rays 4 directions or more H ∩ V ∩ P (HV-convex polyominoes) DTH∩V∩P (h, v) polynomial time [START_REF] Barcucci | Ambiguity results in the characterization of hv-convex polyominoes from projections[END_REF] another open question [START_REF] Gardner | Determination of finite sets by x-rays[END_REF][START_REF] Brunetti | Reconstruction of convex lattice sets from tomographic projections in quartic time[END_REF] Table 1.

C (convex lattice sets) DTC(h, v) open question polynomial time (if uniqueness)

Milestones results

The problem DT C (h, v) that we consider in the paper is very close to the two milestones results (Tab.1). It deals with very simple objects, convex lattice sets, and the most simple directions of X-rays: horizontal and vertical. After twenty years of silence, the question of its complexity became recently subject of a new attention [START_REF] Dulio | First steps in the algorithmic reconstruction of digital convex sets[END_REF].

The complexity of DT C (h, v) has not been yet determined because the principles used for providing the polynomial time algorithms of Tab.1 [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF][START_REF] Brunetti | Reconstruction of convex lattice sets from tomographic projections in quartic time[END_REF] do not hold. First, we don't have the uniqueness property used for the polynomial time algorithm from 4 directions of X-rays [START_REF] Brunetti | Reconstruction of convex lattice sets from tomographic projections in quartic time[END_REF]. There are many ambiguities expressed by boolean variables. Secondly, the combinatorial expression of the convexity constraint requires 3-clauses whereas HVconvexity is expressed by a conjunction of 2-clauses which can be solved in a polynomial time.

Main Result

We prove in the paper that the problem DT C (h, v) of the reconstruction of convex lattice sets with given X-rays can be solved in polynomial for the subclass of the regular convex lattice sets (Fig. 6). Regularity is related with the positions of the points of the lattice set with minimal and maximal abscissa and ordinate. These extreme points are the feet of the lattice set (Fig. 5). Otherwise, S is said regular (Fig. 6). The class of the regular lattice sets (Fig. 6) is denoted R (then the class of the regular convex lattice sets is C ∩ R). The main result of the paper is the following theorem: The time complexity of ConvexTomo is high but polynomial.

A Strategy Passing through Intermediary Results on a New Convex Aggregation Problem

The algorithm ConvexTomo follows the guidelines of the three first steps of the classical polynomial time algorithm designed for the reconstruction of HV-convex polyominoes [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF]. The first step fixes the feet in a regular position (there are a polynomial number of possible positions). Under this assumption, the second step determines some points belonging to all the solutions (the set In) and some other points which can be excluded from all solutions (the set Out). It ends while the so-called filling operations do not allow to determine any new point or if a contradiction follows from a non empty intersection In ∩ Out = ∅ (in this case, the considered position of the feet admits no solution). The set of the remaining undetermined points is a shell between the points of In and the ones of Out. It is denoted Shell. It is the set of the points which might belong to some solutions and be outside from others. These ambiguities are formalized with a decomposition of the shell in combinatorial structures called switching components. After the filling operations, the prescribed X-rays are guaranteed but it remains to determine a configuration of the switching components providing a convex lattice set. Unfortunately, the classical approach encoding convexities with clauses is unable to provide a polynomial algorithm. This combinatorial difficulty is the main challenge to overcome. Our main contribution is a new approach which allows to solve it in polynomial time in the case of the regular lattice sets. This result requires first recent results on regular switching components stated in Property 2 [START_REF] Gérard | Regular switching components[END_REF].

Data: m, n, h ∈ Z n , v ∈ Z m Result: Regular convex lattice set In ⊂ [1, m] × [1, n] verifying H(In) = h and V (In) = v 1 for regular configuration South, East, North, West do 2 /* Step 1 -Initialization of the feet */ 3 Out ← RectangleBorder \ (South ∪ East ∪ North ∪ West) 4 In ← conv R 2 (South ∪ East ∪ North ∪ West) ∩ Z 2 5 NW ∪ NE ∪ SE ∪ SW ← DecompositionIn(Shell)
It requires also a better understanding of the combinatorial problem. It can be seen as a specific problem of Convex Aggregation of either the odd parts, or the even parts of the switching components to the set In. This problem being quite hard to handle, we provide first results on a more generic problem of same nature: Given a finite convex lattice set A ⊂ Z 2 and q finite lattice sets B i called blocks, is it possible to add blocks to In so that their union remains convex?

It is the problem denoted ConvexAggregation(A, B i ). It is stated more precisely in Sect.4 in Problem 2. Under the assumption that the blocks B i can be ordered (their rows and columns are ordered), we provide a polynomial time algorithm for solving it although its expression with boolean variables requires again 3-clauses. The result is stated in Theorem 2. The main idea is that convexity can be controlled through the local property that all the turning angles of the border have the same orientation. The only information that we need to keep in memory for building a convex contour is the last edge. The benefit of the paper is to solve this highly non trivial combinatorial problem DT C∩R (h, v) with a completely new approach. The reduction of the problem of Convex Aggregation to the research of path in a DAG (Property 3) is an intermediary result which has its own interest.

Plan

The polynomial time algorithm ConvexTomo is presented in the following order. We start with the presentation of its three first steps in Sec.3. Then, the problem can be reformulated into a particular question of Convex Aggregation. Before solving it, we need first to investigate a more simple problem of the same kind. Sec.4 is devoted the presentation of generic Convex Aggregation and its reduction to the research of a path in a DAG (Property 3). We adapt the approach for the fourth and last step of the algorithm ConvexTomo with a master DAG and four slave DAGs in Sec.5.

Its final complexity analysis provides a proof of Theorem 1.

3 ConvexTomo -Steps 1/2/3 -From X-rays to Extended

Switching Components

Following the guidelines of the original algorithm presented in [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF] for DT H∩V∩P (h, v), we start by fixing the position of the feet.

Step 1 -Fixing the Position of the Feet and Initialization

The algorithm ConvexTomo investigates all the regular configuration of the feet. One of them being chosen, we can determine that some points are necessary in a solution, if it exists one, while others can be excluded from any solution. This principle is formalized by working with a partition of [1..m] × [1..n] in three sets of points:

-The set In contains the points which are known to belong to all solutions.

-The set Out contains the points which are known to be excluded from all solutions.

-The set Shell is the set of the undetermined points.

Once that the feet have been fixed, we add in Out the points with x = 1 or x = m or y = 1 or y = n which are not in the feet since under the assumption of the considered feet, we are sure that they don't belong to any solution. As we search for a convex solution, we initialize the set In with the convex hull of the feet (Fig. 7).

The convex hull of In provides a partition of the undetermined points (the shell) in four subsets: the North West, North East, South East and South West borders. They are respectively denoted NW, NE, SE and SW (Fig. 7). The assignation of the points of the shell to its four borders NW, NE, SE and SW is done by the function denoted Decomposition In (Shell) in Alg.1.

Complexity Analysis

There are at most m -1 possible positions for each one of the South and the North feet and n -1 cases for the West and East feet. It makes less than m 2 n 2 configurations of the feet to explore.

Step 2 -Filling Operations -FillTomo

Filling operations are widely used in Discrete Tomography and we refer to [START_REF] Brunetti | Fast filling operations used in the reconstruction of convex lattice sets[END_REF][START_REF] Brunetti | Reconstruction of convex lattice sets from tomographic projections in quartic time[END_REF] for a more complete presentation of the operations with suitable data structures.

Starting from the feet, according to the X-rays, the first run of the filling operations fills directly the rows of the West and East feet and the columns of the South and North feet so that it does not remain any undetermined points on these lines. They are all either in In, or in Out.

Notice that just with HV-convexity (we recall that convexity implies HVconvexity), a whole part of the lattice can be quickly determined (Fig. 8).

A run of the filling operations is organized as follows.

1. Fill the rows with the procedure FillRows(In, Out, h). It includes the four filling operations illustrated Fig. 10.

2. Fill the columns with the procedure FillColumns(In, Out, v) under the same principle than for rows. The filling operations used in FillRows(In, Out, h) and FillColumns(In, Out, v). Notice that even if there no point of In in a row, there is always some points of its convex hull (in yellow) that can be used in a similar way. We run the filling operations until falling in one of the two following cases:

-We stop if a run does not allow to determine any new point. It is for instance the case if we have no more undetermined point. In this case, we just have to check the solution. We might also have a set of undetermined points expressing the ambiguity of the input. They express the possibility that different lattice sets can be solutions.

-We stop if a point of In is added in Out or conversely. This contradiction means that the considered position of the feet does not provide solutions.

Complexity Analysis

With suitable data structures, each run of the classical filling operations can be performed in O(mn) time [START_REF] Brunetti | Fast filling operations used in the reconstruction of convex lattice sets[END_REF][START_REF] Brunetti | Reconstruction of convex lattice sets from tomographic projections in quartic time[END_REF]. The complexity do not differ for Algorithm FillTomo. We refer to [START_REF] Brodal | Dynamic planar convex hull[END_REF] for the dynamic update of the convex hull as well as the computation of the hidden points (through the tangents). The time of computation of these two parts can be easily bounded by O(mn) per new determined point.

As FillTomo stops if no new point is determined, the number of runs is at most the number of undetermined points which is bounded by mn.

O(m 2 n 2 ).
Proposition 2. Algorithm FillTomo requires O(m 2 n 2 ) operations.

Step 3 -Computing the Switching Components -

SwitchingComponents

The third step of ConvexTomo occurs only if it remains undetermined points. Their set, the shell has a lot of properties. If an undetermined point p = (i, j) is in a South border SW ∪ SE, then the point denoted p = (i, j + v i ) is a North undetermined point (otherwise the filling operations would have determined (i, j)). We define them as vertical correspondents. In the same way, any West undetermined point |p = (i, j) has an horizontal East correspondent p| = (i + h j , j) (Fig. 11). Horizontal and vertical correspondences are symmetric relations.

Their main property is the following:

Property 1.
We consider an instance DT C (h, v) with a position of the feet leading to undetermined points at the end of the filling operations. For any solution S of DT C (h, v), an undetermined point p is in S if and only if its correspondents are not in S.

Proof. Corresponding points cannot be both in S because their distance is h j (horizontally) or v i (vertically) would lead to have too many points in the row or column of p. Conversely, they cannot be both outside from S because otherwise, it does not remain enough points between them to have the prescribed number of points on its row or column.

Starting from an undetermined point p 1 , a sequence of correspondents can be defined by induction: the point p 2k is the horizontal correspondent of p 2k-1 while p 2k+1 is the vertical correspondent of p 2k . As the set of the undetermined points is finite, the sequence is cyclic. The classical approach developed in [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF] for reconstructing HV-convex polyominoes is to search for an assignment of the boolean variables leading to an HV-convex solution S. The approach passes through the encoding of the HV-convexity constraint in a conjunction of 2-clauses. It leads to a 2-SAT instance (Fig. 13). Convexity can be also be encoded with clauses (Fig. 13) but 3-clauses might be necessary with the difficulty that 3-SAT is no more polynomial but NP-complete. This obstruction is the main difficulty of the reconstruction of convex lattice sets. The new approach presented in next Sec.5 requires some properties proved very recently on regular switching components [START_REF] Gérard | Regular switching components[END_REF]. We summarize these properties as follows.

Property 2. (i) With a regular position of the feet, all the switching components have a constant turning angle (they are called regular).

(ii) By choosing p 1 in NW (it is always possible), for any k, we have (iv) The points of different extended switching components can share neither a row, nor a column. (v) The switching components can be ordered according to their rows (or equivalently according to their columns). They cannot interlace.

p 1+4k ∈ NW, p 2+4k ∈ NE, p 3+4k ∈ SE, p 4k ∈ SW. (
The algorithm SwitchingComponents decomposes the shell in switching components and then merges them in extended switching components.

Complexity analysis

The computation is linear in the number of undetermined points. It requires no more than O(mn) operations.

Proposition 3. Algorithm SwitchingComponents takes O(mn) time.

Problem of Convex Aggregation

The three first steps of Algorithm ConvexTomo led to a stage where any assignment of the switching components provides the requested X-rays. On the left, due to convexity, the switching components P 1 , P 2 , P 3 , P 4 are necessarily equal while P 5 is independent. On the right, we merge P 1 , P 2 , P 3 , P 4 in the extended switching component P 1 and P 5 becomes P 5 . The extended switching components are on different rows and columns. They can also be ordered according to their rows (or columns).

The convexity of the solution is however not yet guaranteed. The approaches of the state of the art do not allow to overcome this difficulty.

Therefore, we explore a new class of problems dealing with Convex Aggregation. We reduce it to a question of reachability in a Directed Acyclic Graph. In the following section, we use this tool to provide the final step of Algorithm ConvexTomo.

Problem Statement

We consider a new problem of Convex Aggregation of blocks along a convex set. The problem can be stated as follows:

Problem 2 (ConvexAggregation(A, B i )).

Input: -A convex lattice set A ⊂ [0..s] × [0..t] with {(0, 0), (s, t)} ⊂ A -a finite sequence of q lattice sets that we call blocks

B i ⊂ [0..s] × [0..t]
disjoined from A, above the diagonal from (0, 0) to (s, t), with increasing abscissa and ordinates so that for any i < j, (x, y) ∈ B i , (x , y ) ∈ B j , we have x < x and y < y .

Output: Does there exist a convex union A ∪ (∪ i∈I B i ) where I is a non empty subset of the indices from 1 to q (Fig. 15)?

We could also generalize the problem with a given non convex lattice set A. In this case, the first step of an approach would be to fill the non-convex parts of A with blocks and repeat this process until finding a Convex Aggregation. There is no combinatorial difficulty with such an instance. The problem becomes of interest if we start from a set which is already convex and search for a non trivial Convex Aggregation of blocks.

We can assume without loss of generality that the set A contains the point (s, 0) and fills the triangle below the diagonal from (0, 0) to (s, t).

The reason is that the blocks B i being above the diagonal, the edges of the convex hull of A below the diagonal remain unchanged. The combinatorial problem is above. ) and its solution. On the left, the input is a convex lattice set A and a sequence of lattice sets B i . On the right the output is a non empty union of B i so that their union with A is still convex. It means that some of the sets B i have to be aggregated with A and some others discarded (for instance the green and the red sets in the suggested solution).

We could encode the choice to add or reject a block B i by a boolean variable but as previously (Fig. 13), the convexity is expressed by a conjunction of 3-clauses that 3-SAT algorithms cannot necessarily solve in polynomial time. It is the same difficulty than the one presented in the framework of DT C (h, v).

Rewriting ConvexAggregation(A, B i )] with a Directed Acyclic Graph

We provide a new approach by reducing the problem to the research of a path joining two subsets in a Directed Acyclic Graph. Let us consider a solution A∪ i∈I B i of the instance ConvexAggregation(A, B i ) as drawn in det( -→ vv , -→ vp) ≤ 0 (large inequality) (Fig. 16).

To complete the notations, given a block B i , we denote H i the minimal horizontal strip containing all the points of the block (

H i = {(x, y)| ∃(x , y ) ∈ B i , ∃(x , y ) ∈ B i , y ≤ y ≤ y }).
Notice that due to the increasing assumption on the blocks in ConvexAggregation(A, B i ), the horizontal strips H j are ordered and disjoined.

There are bipoints with vertices in U which can clearly not appear in the contour of a solution of ConvexAggregation(A, B i ). We want to exclude them. We define the set V as the set of bipoints of U ×U obtained by removing from U × U any bipoint -→ pp ∈ V × V (Fig. 16) This condition is the key to build the DAG that we use to solve Problem ConvexAggregation(A, B i ) (Fig. 17).

1
We have however to take care to avoid inconsistent concatenation of bipoints as for instance drawn in Fig. 17. A path which is passing on the left of some points of a block B i should not be able to pass further on the right of B i . A solution to forbid such inconsistent concatenation is first to duplicate the bipoints included in the horizontal strip H i of a block B i but also, without any point of B i neither on its left, nor on its right. This case is illustrated in the lower part of Fig. (ii) there is no outlier on the right of

-→ pp (([0..s] × [0..t] \ (A ∪ 1≤i≤n B i )) ∩ Right( -→ pp ) = ∅), (iii) there is no point of A on the left of -→ pp (A ∩ Left( -→ pp ) = ∅),
(iv) there are no pair of points of the same block B i on the right and on the left of -→ pp (for any index i,

B i ∩ Left( -→ pp ) or B i ∩ Right( -→ pp ) is empty).
The final set V is obtained from V by duplicating the bipoints -→ pp in-Fig. 17. Critical cases. On the left, we have two configurations which might lead to inconsistent concatenation of bipoints with points of B i on both sides of the path. We avoid this problem by adding labels (or colors). Labeling is sufficient to solve the case above, but not the one below. The reason is that the intermediary bipoint might be used for a path with the block B i on its left or on its right (we did no assumption on the connectivity or convexity of the blocks). To avoid inconsistency, we duplicate this bipoints and provide a copy with the two possible labels (or colors).

cluded in the horizontal strip H j of a block B i but with no point of B i in

Left( -→ pp ) ∪ Right( -→ pp ). The copy is denoted -→ pp * .
We label now the bipoints of V in order to avoid inconsistent paths.

The labels are registered in a vector of dimension q where q is the number of blocks B i . Definition 6. For any index i from 1 to q, the label of the bipoint

-→ pp ∈ V of index i is denoted -→ pp [i]
and we have:

-→ pp [i] = 1 if B i ∩ Right( -→ pp ) is not empty, -→ pp [i] = -1 if B i ∩ Left( -→ pp ) is not empty, -→ pp [i] = 0 otherwise, except if the bipoint is included in the strip H i . In this specific case, -→ pp [i] = -1 for the original bipoint -→ pp and -→ pp * [i] = 1
for its copy. Definition 7. We consider the DAG G A,B i = (V , E). Its vertices are the bipoints of V . We have an edge from the bipoint

-→ pp ∈ V to the bipoint --→ p p ∈ V if -the angle ( -→ pp , --→ p p ) turns clockwise (det( -→ pp , --→ p p ) < 0), -and, if p is in the horizontal strip H i of the block B i , then -→ pp [i] = --→ p p [i].
We reduce the problem ConvexAggregation(A, B i ) to the research of a path from a bipoint starting at the origin to a bipoint ending at point (s, t).

Property 3. The set of bipoints

-→ pp where p = (0, 0) is denoted V 0 while the set of bipoints

-→ pp where p = (m, n) is denoted V 1 .
The instance ConvexAggregation(A, B i ) admits a solution if and only if the DAG G A,B i admits a non trivial path from the set V 0 to the set V 1

(the trivial path is the convex border of A excluding all the blocks B i .

All labels are -1).

Proof. First, a solution of ConvexAggregation(A, B i ) has a convex path from the origin to (s, t). By taking its consecutive pairs of vertices as bipoints, we have a sequence of bipoints turning clockwise, starting from a bipoint with the origin in (0, 0) and going to a bipoint with its end in (s, t). If they are all in V and verify the conditions of concatenation, they provide a path going from V 0 to V 1 in the DAG. Both conditions follow directly from the definitions.

Secondly, we consider a path going from

V 0 to V 1 in the DAG G A,B i .
The concatenation condition on the labels guarantees that the path passes either on the left, or on the right of any block. The orientation condition (clockwise angle) guarantees the convexity of the path, and the condition that each bipoint has no outlier on its right guarantees that the set of the points on the right of the path is the union of A with the blocks providing labels equal to +1.

It remains to notice that the trivial solution of ConvexAggregation(A, B i ) corresponds to the excluded path with all labels equal to -1.

According to Property 3, we can solve ConvexAggregation(A, B i ) by searching for a non trivial path from

V 0 to V 1 in the DAG G A,B i . Starting
from the bipoints of V 0 , we use a depth-first search to to determine if V 1 is reached. At each vertex (bipoints) of the graph, we give the priority of exploration to the following bipoints having a first non null label equal to +1 or before -1. With this strategy, the trivial path is the last one to be explored, so that the requested result is obtained before considering it.

Complexity Analysis The number of upper vertices of the sets

A ⊂ [0..s] × [0..t] and of the disjoined blocks B i ⊂ [0..s] × [0..t] is at most s + s.
Therefore, the number of bipoints in V is in O(s 2 ). With duplications, it provides the number of vertices of the DAG in O(s 2 ). It remains to count the number of edges. Edges are no more than triangles. Their number is in O(s 3 ).

About the time to create the DAG G A,B i , we need first to compute all the upper vertices of the convex hulls of A and the blocks. We can assume that the lattice points are ordered so that the total time is bounded by O(st) (ordered lattice sets provide simple polygons whose convex hulls can be computed in linear time [START_REF] Mccallum | A linear algorithm for finding the convex hull of a simple polygon[END_REF]). It provides the set U .

Then we have to check the conditions required for a bipoint of U × U to belong to V . The condition (i) is trivial while each one of the conditions (ii) (iii) and (iv) can be resolved in O(st) with a naive algorithm. The labels are also computed in O(st). With O(s 2 ) possible bipoints in V , we obtain O(s 3 t) for the computation of V .

The determination of the valid edges of the DAG (clockwise turning angle and label's consistency) can be done in constant time for each pair of bipoints (or triangle) and therefore with a total time in O(s 3 ).

The depth-first search algorithm used to determine whether V Without the relations induced by the switching components on each border, we would have four independent problems of Convex Aggregation ConvexAggregation(A, B i ) as solved in previous section (Fig. 19). The difficulty comes from the fact the four problems are not independent but deeply related: If the block B i NW is added in the North West border NW, the block B i SE of the same extended switching component in SE has also to be aggregated while the corresponding blocks B i NE and B i SW in NE and SW have to be discarded (Fig. 19). We could think about exploring the sets of solutions on the four border in order determine whether a combination of solutions might be consistent but the potential exponential number of solutions makes this approach potentially non polynomial. We have to solve simultaneously the four related problems of Convex Aggregation.

The principle that is we use is to build a new DAG that we call the master DAG coordinating the aggregation on each border.

V 0 ⊂ V 0 NW × V 0 NE × V 0 SE × V 0 SW . In the same way, V 1
is the set the valid 4-tuples of bipoints ending at the North and South feet

V 1 ⊂ V 1 NW × V 1 NE × V 1 SE × V 1 SW .
The instance DT C∩R (h, v) admits a solution if and only if there is path

in the master DAG G = (V, E) from V 0 to V 1 .
Proof. We have to prove that a solution of DT C∩R (h, v) provides a path from V 0 to V 1 in the master DAG G and conversely that a path in the DAG provides a convex lattice set with the prescribed X-rays.

For the first assertion, we have a convex solution with a contour between the four feet. The main point is to show that we can advance on the different borders from the East and West feet to the South and North feet by using only valid 4-tuples of bipoints and valid edges (valid according to the definition of the master DAG). The consistency of the 4-tuples of bipoints that can be extracted from the contour is straightforward but not the continuity. There are however strategies which allow to guarantee this property at each step: we move the bipoint with the less advanced starting point with respect to the horizontal strips H i of the switching components (as illustrated in Fig. 20). By induction, the continuity of 4tuples of bipoints (which is true in V 0 ) is guaranteed. It provides the first assertion.

For the converse, each path in the master DAG from V 0 to V 1 provides a path in the slave DAGs. Theorem 2 insures that each one of these paths defines a convex contour with blocks on the left and blocks on the right.

It remains to prove that the contours on each border are consistent.

We have a first property: following the path in the DAG until a 4-tuple Let us show now that the contour gradually built from the path in the DAG is consistent. We prove it again by induction. With the consistency condition, it is true for the initial 4-tuple of bipoints. Then we assume that the contour generated by the path is consistent until the vertex therefore provides a convex lattice set with the prescribed X-rays.

of bipoints ( ---→ w NW , --→ w NE , --→ w SE , --→ w SW ), if
( ---→ w NW , --→ w NE , --→ w SE , --→ w SW ).

Algorithm ConvexAggregation

The The final part of the algorithm is the research of a path starting from V 0 and reaching V 1 . It can be done with depth-first or breadth-first search.

Complexity Analysis

We start with the computation of the slave DAGS. According to the previous analysis, by replacing (s, t) by the upper bound (m, n), it can be done in O(m 3 n).

For the master DAG, as we have at most m 2 bipoints in each slave DAG, the number of 4-tuples of bipoints in V is bounded by O(m 8 ). For each one of them, testing their validity requires O(q). The computation of the vertices of the master DAG takes O(qm 8 ).

For going from the vertex (

------→ p NW p NW , ------→ p NW p NW , ------→ p NW p NW , ------→ p NW p NW )
V 0 ← V ∩ V 0 NW × V 0 NE × V 0 SE × V 0 SW ; 9 V 1 ← V ∩ V 1 NW × V 1 NE × V 1 SE × V 1 SW ; 10 /* Search for a path from V 0 to V 1
*/ 11 path ← searchPath(V, E, V 0 , V 1 ); 12 readLabels(path) Notice that if n < m, with a rotation of π 2 , it could be as well O(n 9 ).

Conclusion

The problem of the reconstruction of convex lattice sets with prescribed horizontal and vertical X-rays is the most challenging problem of complexity in the framework of Discrete Tomography. The question is to determine whether we can handle with ambiguous X-rays and convexity constraints in polynomial time.

The paper is a first step in the direction of a better understanding of the relations between ambiguities and convexity.

Fig. 1 .

 1 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.

Definition 1 .

 1 Given a finite lattice set S ⊂ [1..m] × [1.

Fig. 2 .

 2 Fig. 2. 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).

Fig. 3 .

 3 Fig. 3. A convex lattice set is equal to the intersection of its convex hull (in yellow) with the lattice Z 2 .

Fig. 4 .

 4 Fig. 4. Classical problem of reconstruction. The problem of reconstruction of a lattice set with prescribed horizontal and vertical X-rays can be reformulated in terms of flows in a bipartite graph. It can also be solved with the polynomial time algorithm of H.J. Ryser [25].

Fig. 5 .Definition 3 .

 53 Fig. 5. The four feet of a lattice set S are denoted South, West, North and East.

Fig. 6 .

 6 Fig. 6. Regular lattice sets are the lattice sets such that there exists no integer point (X, Y ) (represented by the green cross) separating the pairs of feet in opposite corners.

Theorem 1 .

 1 The algorithm ConvexTomo solves DT C∩R (h, v) with a worst case time complexity in O(m 4 n 4 + m 11 n 2 ) where we can assume m ≤ n.

  This deep property allows to solve ConvexAggregation(A, B i ) in polynomial time by reducing it to the research of a path connecting two subsets of vertices in a Directed Acyclic Graph (DAG) (Property 3). If we come back to the problem of Discrete Tomography DT C∩R (h, v), it can be seen as four related problems of Convex Aggregation. We build one DAG per problem and call them the slave DAGs. Then the relations between the four solutions that we search for are controlled by building a fifth DAG that we call master DAG. It allows to encode the existence of a solution of DT C∩R (h, v) with the considered feet in the existence of a path joining two regions of the master DAG (Theorem 3). It provides the fourth and final step of the algorithm ConvexTomo reconstructing a convex solution of DT C∩R (h, v) in polynomial time if there exists one.

Fig. 7 .

 7 Fig. 7. Fix the feet and Initalize In, Out, NW, NE, SE and SW. On the left, the different possible positions of the feet. We do not consider the irregular configurations. In the middle, a regular position of the feet is chosen. The other points with x = 1 or x = m or y = 1 or y = n are added in Out (in red). The shell (in grey) is the set of the points which are not yet determined. On the right, due to convexity, we can add to In not only the four feet but directly the lattice points of their convex hull. The shell is thus decomposed in four subsets NW, NE, SE and SW according to their position relatively to the convex hull of In.

Fig. 8 .

 8 Fig. 8. Filling from the feet. Starting from the feet, the filling operations allow to fill directly an important part of the lattice. In one run, we obtain a figure that can be summarized in the right drawing, where the undetermined points are only in the white zones.

3 .

 3 As we search for convex solutions, if In has been updated in the previous steps, we complete the update by replacing it by its discrete convex hull (In ← convv(In) ∩ Z 2 ).

4 .

 4 If In or Out have been updated in the three previous steps, we complete Out by all the hidden points (a point x is hidden if conv R 2 ({x} ∪ In) ∩ Out = ∅ -Fig.10). 5. Update the four borders SE, NE, NW and SW of the shell.

Fig. 9 .

 9 Fig. 9.The filling operations used in FillRows(In, Out, h) and FillColumns(In, Out, v). Notice that even if there no point of In in a row, there is always some points of its convex hull (in yellow) that can be used in a similar way.

Fig. 10 .

 10 Fig. 10. The filling operations including the points of the convex hull of In and excluding the undetermined points hidden by a point of Out. On the left, we assume that new points of In and Out have been determined (the six large disks). Then we compute the new convex hull with the new points of In and use the tangent lines of the points of Out to compute the hidden zones (in pink).

Fig. 11 .

 11 Fig.11. Corresponding points. On the left, the undetermined points are drawn in grey in white cells. In the middle, a pair of vertical correspondents (green) and a pair of horizontal correspondents (blue). We represent the corresponding points alternatively with squares or diamonds. Notice that the segment represented by the dotted ellipse has only two possible positions. Due to its length, if it contains the square, it does not contain the diamond and conversely. On the right, the correspondences define closed paths called switching components which provide a partition of the undetermined points. For each switching components, either the squares, or the diamonds belong to a solution.

Definition 4 .

 4 A switching component P is a closed path of alternatively horizontal and vertical corresponding undetermined points (Fig.12).The switching components provide a partition of the shell. Due to Property 1, either the points with even indices, or the points with odd indices belong to a solution S. This binary state of the switching component with regard to a solution S can be encoded by a boolean variable denoted P (S). We choose P (S) = 1 if the points with odd indices are in S and P (S) = 0 otherwise.

Fig. 12 .

 12 Fig.12. Switching components. In each switching component, the squares represent the points with odd indices and the diamonds the ones with even indices. Either the squares, or the diamonds of a switching component are in a solution. In the two left cases, the feet are in a regular position, while we have an irregular position of the feet on the right. In this case, the switching components might have a different structure with turning sometimes clockwise and sometimes anticlockwise. Such switching components are said irregular but they don't occur in the regular case that we investigate.

  iii) The switching components which have two points at Euclidean distance 1 are considered as connected. This symmetric relation leads to define the connected components of switching components that we call extended switching components. The extended switching component of a switching component P is denoted P . HV-convexity enforces all the switching component of P to be equal to P . Either the points of the NW and SE borders of P (represented by squares in Fig.12) belong to S, or the points of NE ∪ SW (represented by diamonds) are in S. For the following, we assume that the extended switching components are unstructured sets obtained by union of the points of the connected sequences.

Fig. 13 .

 13 Fig. 13. 2 and 3 clauses encoding convexity. HV-convexity is expressed by a conjunction of 2-clauses. Thus, the research of an HV-convex solution is reduced to a 2-SAT instance that can be solved in polynomial time. Expressing convexity in the same manner, might require 3-clauses with the difficulty that 3-SAT is NP-complete.

Fig. 14 .

 14 Fig.14. Extended switching components. On the left, due to convexity, the switching components P 1 , P 2 , P 3 , P 4 are necessarily equal while P 5 is independent. On the right, we merge P 1 , P 2 , P 3 , P 4 in the extended switching component P 1 and P 5 becomes P 5 . The extended switching components are on different rows and columns. They can also be ordered according to their rows (or columns).

Fig. 15 .

 15 Fig.[START_REF] Gardner | Geometric Tomography. Encyclopedia of Mathematics and its Applications[END_REF]. An instance of ConvexAggregation(A, B i ) and its solution. On the left, the input is a convex lattice set A and a sequence of lattice sets B i . On the right the output is a non empty union of B i so that their union with A is still convex. It means that some of the sets B i have to be aggregated with A and some others discarded (for instance the green and the red sets in the suggested solution).

Fig. 15 .

 15 Fig.15. The possible vertices of the upper hull of a solution are necessarily upper vertices of A or upper vertices of a block B i . The set of all these upper vertices is denoted U . Then the set of the upper edges of a solution is included U ×U . We orient them and call them bipoints in order to avoid the possible ambiguities with other edges considered in the following. Let us consider a bipoint -→ vv ∈ U × U between two vertices v = (x 0 , y 0 ) and v = (x 1 , y 1 ) in U with y 0 ≤ y 1 . We define its left Left( -→ vv ) as the set of points p ∈ [0..m] × [y 0 ..y 1 ], verifying det( -→ vv , -→ vp) > 0 (strict inequality) while its right is the set of points p ∈ [0..m] × [y 0 ..y 1 ] verifying

  . with x > x or with x = and y > y (we keep only the bipoints going to the right or upward), 2. or having on its right (in Right( -→ pp )) a lattice point which is not in A ∪ 1≤i≤n B i (such point are called outliers), 3. or with a point of A on its left (in Left( -→ pp )), 4. or with points of the same block B i on its right (B i ∩ Right( -→ pp ) non empty) and on its left (B i ∩ Left( -→ pp ) non empty). Let us come back to a solution A ∪ i∈I B i of the instance Convex Aggregation(A, B i ). The upper path connecting the origin to the point (s, t) is the concatenation of bipoints of V . Convexity is expressed by the property that two consecutive bipoints -→ pp and --→ p p turn always clockwise.

Fig. 16 .

 16 Fig. 16. The excluded bipoints. Let us precise that, although the shapes drawn in this figure appear to be continuous, they represent discrete lattice sets. Above, the sets Left( -→ pp ) and Right( -→ pp ). Below, we exclude the bipoints with an outlier on their right, with a point of A on their left, and with a pair of points of the same block on both sides. They are excluded because they are surely not contour bipoints of a solution of ConvexAggregation(A, B i ).

17

 17

Definition 5 .

 5 . Such duplication leads to define a new set of bipoints that we denote V . We complete now the definitions: Let U be the set of the upper vertices of the convex hulls of the sets A and of the blocks B i . Let p(x, y) and p (x , y ) be a pair of vertices in U .The set V is the set of bipoints -→ pp ∈ V × V satisfying the four conditions:(i) y > y or if y = y, x > x where (x, y) and (x , y ) are respectively the coordinates of p and p ),

Fig. 18 .

 18 Fig. 18. Labels. The labels of the bipoint -→ pp are [-1, -1, 1, 0] since it passes to the right of the two previous blocks B 1 and B 2 , to the left of B 3 and does not cross the horizontal strip H 4 of B 4 .

5

  ConvexTomo -Steps 4 -Convex Aggregation of the Extended Switching Components 5.1 Reformulation of the Problem in Terms of Convex Aggregation At the end of the third step of the algorithm ConvexTomo, the set In and the extended switching components have been computed. It remains to find a assignment of the extended switching components providing a convex solution. According to Property 2, for each extended switching component, we have the choice between aggregating its North West and South East parts (represented with squares if the figures) or its South West and North East parts (the diamonds in the figures) to the set In. Thus, the blocks are the subsets of the extended switching components in each border NW, NE, SE and SW. The block B i of the North West border is for instance B i NW = P i ∩ NW. Property 2 (different extended switching components have neither rows, nor columns in common) guarantees the growing property of the blocks assumed in ConvexAggregation(A, B i ).

Fig. 19 .

 19 Fig.[START_REF] Gérard | Regular switching components[END_REF]. Convex Aggregation of switching components and corresponding DAGs. After the third step, the algorithm ConvexTomo provides a decomposition of the undetermined points in extended switching components (with colored squares and diamonds). For each color, we aggregate either the squares, or the diamonds to the set In with the goal to provide a convex lattice set. It's the problem of Convex Aggregation that we address to conclude the paper. We start by building four DAGs GNW, GNE, GSE and GSW corresponding to the four rectangles drawn on the right. The four problems are considered upward for the North borders and downward for the South borders so that the switching components provide blocks in the same order.

5. 2 Theorem 3 .

 23 Building the Master DAG We place us after the third step of the algorithm ConvexTomo for an instance an instance DT C∩R (h, v) with a regular position of the feet. At this stage, the extended switching components P i and the convex set In have been computed. We start by defining the four DAGs G NW , G NE , G SE and G SW with a subset of In as convex set A and with the switching components B i NW = P i ∩ NW as block B i and the same for the three other borders. According to the ordering of the blocks, the fours DAGs 5.3 Equivalence between a Path in the Master DAG and a Convex Aggregation of the Related Blocks We prove the following theorem: We consider an instance DT C∩R (h, v) with a regular position of the feet providing after the third step of algorithm ConvexTomo q switching components P i . The slave DAGs G NW , G NE , G SE and G SW and the master DAG G = (V, E) being defined according to Definition 8, we denote V 0 the 4-tuples of vertices (w NW , w NE , w SE , w SW ) with all bipoints w starting from the West and East feet

  a label of one of the bipoints (for instance ---→ w NW [i]) is not null, then all the labels which have been visited and determined by the path after the index i have non null values for at least one of the bipoints of the 4-tuple. This property denoted (i) can be established by induction. It is obvious for the initial 4-tuple of bipoints (due to the consistency condition) and it remains true by induction due to the continuity condition of the 4-tuple of bipoints.

  fourth step of Algorithm ConvexTomo solves the problem of Convex Aggregation issued from the switching components through the research of a path in the master DAG G. The algorithm ConvexAggregation starts by computing the four slave DAGs. Then it considers all the 4-tuples of bipoints in V NW × V NE × V SE × V SW and checks their validity. Afterward, it computes the edges of the master DAG by checking the validity and the turning angle of the pairs of vertices.

Algorithm 3 :Theorem 4 .

 34 ConvexAggregation(m, n, In, (P i ) 1≤i≤q ) p NW ∈ NW, and then checking if (------→ p NW p NW , ------→ p NW p NW , ------→ p NW p NW , ------→ p NW p NW )is a valid vertex. It checks also whether the pair (------→ p NW p NW , ------→ p NW p NW ) is in E NW .The number of edges is bounded by the number of vertices O(m 8 ) times the number of possible new points 2m. It makes a number of edges in O(m 9 ). The time necessary to check their validity is constant with a suitable data structure containing the edges of the slave DAGs. With the number of vertices and edges, the breadth-first search can be done in O(m 9 ). As q is lower than m, it provides a total time of computation in O(m 9 ). It proves the following theorem. Algorithm ConvexAggregation(m, n, In, (P i ) 1≤i≤q ) solves the problem of Convex Aggregation of the blocks issued from the switching components in [0..m] × [0..n] with a worst case time complexity in O(m 9 ).

5. 5

 5 Proof of Theorem 1 Theorem 4 provides the time complexity in O(m 9 ) of the algorithm Convex Aggregation. According to the propositions 1, 2, 3, the three first steps (Initialization, FillTomo, SwitchingComponents) require respectively O(mn), O(m 2 n 2 ) and O(mn) operations. Since there are at most m 2 n 2 regular positions of the feet to explore, the overall time complexity of Algorithm FillTomo is O(m 4 n 4 + m 11 n 2 ), as stated in Theorem 1.

  The ambiguities are expressed by the switching components. After the three first steps of the classical algorithm, they lead to reduce the problem to a question of Convex Aggregation. The new idea that we present is that discrete convexity is a local constraint. It can be reduced to the property that consecutive edges have a clockwise turning angle. Such a constraint can be handled with a DAG or more generally with Dynamic Programming.The crucial information is the last reconstructed edge so that we can try to go further. These two elements (switching components and encoding of the last edge) allowed us to develop the polynomial time algorithm ConvexTomo in the case of a regular position of the feet. It is a good news but why not a more general result ? What happens in the case of an irregular position of the feet which is different than for the regular positions ? The answers can be reduced to only one word: "structure".The structure of the regular switching components can be simplified by merging them into extended switching components. According to recent combinatorial results (Property 2[START_REF] Gérard | Regular switching components[END_REF]), extended switching components can be ordered (their rows and columns are ordered) so that the consecutive blocks to consider in a Convex Aggregation framework are also well ordered. This order (or increasing property) is the only assumption that we did on the blocks in problem ConvexAggregation(A, B i ).Without it, there is no doubt that Convex Aggregation would become NP-hard. Structural properties are necessary to provide polynomial time algorithms of Convex Aggregation. This remark leads to the following question: with irregular positions of the feet, do switching components (Fig.12) have enough structures to be handled with polynomial time algorithms ? It's an open question whose answer could as well lead to a polynomial time algorithm as to a result of NP-completeness.

Fig. 20 .

 20 Fig.20. A path in the master DAG and the corresponding solution of DTC∩R(h, v). We show why any solution of DTC∩R(h, v) can be obtained through a path from V 0 to V 1 in the master DAG. The path is obtained with the strategy to advance the bipoint -→ vv with the less advanced point v regarding the horizontal strips H i of the switching components. With this strategy, the continuity of the labels is guaranteed by induction.

1

  FillTomo Data: m, n, v ∈ Z m , h ∈ Z n and four borders In, Out, NW, NE, SE, SW Result: Sets In, Out, SE, NE, NW and SW under the assumption of the given feet 2 while SE, NE, NW or SW have been decreased do

	3	/* Filling operations	*/
	4	FillRows(In, Out, h);
	5	FillColumns(In, Out, h);

6

In ← conv R 2 (In) ∩ Z 2 ; 7 Out ← ShadowIn(Out) ∩ Z 2 ; 8 /* Remove new determined points from SE, NE, NW or SW */ 9 Decrease(SE, NE, NW, SW, In, Out); 10 if In ∩ Out = ∅ then 11 return("no solution"); 12 end 13 end Algorithm 2: FillTomo(m, n, v, h, In, Out, NW, NE, SE, SW) Therefore, the overall time complexity of the function FillTomo is in

  1 can be reached from V 0 takes a linear time in the number of vertices and edges i.e O(s 2 + s 3 ) = O(s 3 ). By counting the time necessary to build the graph and to search for a solution, we have (without optimization) a worst-case time complexity in O(s 3 t). It proves the following theorem. Theorem 2. The problem ConvexAggregation(A, B i ) in [0..s] × [0..t] can be solved in O(s 3 t).

  According to the set of edges E, we can assume

	w.l.g that the next vertex is ( ---→ w NW , --→ w NE , --→ w SE , --→ w SW is inconsistent for the switching component of index j, it means that --→ w SW ). If the new bipoint
	the index already had in the path a non null label. Due to property (i),
	this label is also non null value in the current 4-tuple. As there was no inconsistency before, it follows that --→ w SW has an inconsistent label with one of the three bipoints ---→ w NW , --→ w NE , --→ w SE . It's in contradiction with the consistency of the 4-tuple ( ---→ w NW , --→ w NE , --→ w

SE , --→ w SW ). It proves that the contour built from the path in the master DAG is a valid solution and

  In and the extended switching components (P i ) 1≤i≤q Result: An assignment of the extended switching component providing a convex aggregated set 1 /* Compute the slave DAGs GNW, GNE, GSE and GSW with labels */ 2 (VNW, ENW) ← DAG(In, (P i ) 1≤i≤q ∩ NW); 3 (VNE, ENE) ← DAG(In, (P i ) 1≤i≤q ∩ NE); 4 (VSE, ESE) ← DAG(In, (P i ) 1≤i≤q ∩ SE); 5 (VSW, ESW) ← DAG(In, (P i ) 1≤i≤q ∩ SW); 6 /* Compute the master DAG */ 7 (V, E) ← masterDAG((VNW, VNE, VSE, VSW, ENW, ENE, ESE, ESW, labels); 8

to one of its successors, we have to introduce a new upper point, for instance Data: m, n,

are oriented upward for the North borders and downward for the South borders (Fig. 19) so that the blocks B i of the switching components appear in the same order. The vertices of the DAGs are V NW , V NE , V SE and V SW and their edges E NW , E NE , E SE and E SW as defined in Definition 7. We call them the slave DAGs. Then we define the master DAG as follows:

V SE × V SW verifying two conditions (letter w represents bipoints):

-Label's consistency-for any index i from 1 to q, the labels ---→ w NW [i],

--→ w SE [i] are of same sign (with the convention that 0 is both positive and negative). The labels --→ w NE [i] and --→ w SW [i] are also of same sign and it is the opposite from the previous pair.

-Label's continuity-If there is null label for the four bipoints ( ---→

We have an edge from

if three of the bipoints are unchanged (for instance ---→


Jean-Christophe Aval

On sets represented by partitions

We prove a lemma that is useful to get upper bounds for the number of partitions without a given subsum. From this we can deduce an improved upper bound for the number of sets represented by the (unrestricted or into unequal parts) partitions of an integer n.

Introduction

Let n be an integer and let

n = n 1 + n 2 + ... + n j , n i ∈ IN * , 1 ≤ n 1 ≤ n 2 ≤ ... ≤ n j
be a partition Π of n. We shall say that this partition represents an integer a if there exist ǫ 1 , ǫ 2 , ..., ǫ j ∈ {0, 1} such that a = j i=1 ǫ i n i . Let E(Π) denote the set of these integers; we shall call it the set represented by Π. One can easily see that E(Π) is included in [0, n] and symmetric (if it contains a, it also contains n -a). For fixed n, let us introduce p(n) the number of partitions of n and p(n) the number of different sets amongst the sets E(Π) (where Π runs over the p(n) partitions of n).

Let k be a positive integer. We shall say that a partition is k-reduced if and only if each summand appears at most k times; for instance the 1reduced partitions are the partitions into unequal parts. We shall use q(n, k) the number of k-reduced partitions of n and q(n, k) the number of different E(Π) where Π runs over the q(n, k) k-reduced partitions of n. When k equals 1, we shall note: q(n) = q(n, 1) and q(n) = q(n, 1).

Following an idea due to P. Erdös, the sets represented by the partitions of an integer n were first studied at the end of the 80's. P. Erdös, J.-L. Nicolas and A. Sárközy (cf. [START_REF] Erdös | On the number of partitions of n without a given subsum II, Analytic Number Theory[END_REF]) obtained upper bounds for the number of partitions without a given subsum. P. Erdös then proposed to study the asymptotic behaviour of p(n) and q(n). In [START_REF] Delglise | Sur les ensembles reprsents par les partitions d'un entier n[END_REF] and [START_REF] Nicolas | On two partition problems[END_REF], M. Delglise, P. Erdös, J.-L. Nicolas and A. Sárközy proved the following estimates: Theorem 1: For n large enough, one has

q(n) 0.51 ≤ q(n) ≤ q(n) 0.96 and p(n) 0.361 ≤ p(n) ≤ p(n) 0.773 .
We shall obtain the following improved upper bounds:

Theorem 2: For n large enough, one has

q(n) ≤ q(n) 0.955 and p(n) ≤ p(n) 0.768 .
To get these new exponents, we shall prove in part 2 a lemma improving a result due to J. Dixmier [START_REF] Dixmier | Partitions avec sous-sommes interdites[END_REF], whose application in part 3 gives the announced improvements.

The main lemma

Let a be an integer, a ≤ n. We introduce R(n, a), the set of partitions of n that do not represent a, and R(n, a) shall denote its cardinality. In the case of partitions into unequal parts, we shall need the same notions, with the similar notations Q(n, a) and Q(n, a). We shall also define Q(n, a, 2) as the number of 2-reduced partitions Π of n such that a is not represented by Π.

Lemma 1: Let ǫ > 0. Assume there exists δ ∈]0, 1[ such that, for any integer n and for any integer a, the following property holds

(1) ǫ √ n -1 ≤ a ≤ 2ǫ √ n ⇒ R(n, a) ≤ p(n) δ .
Then, for n large enough, one has

j 2 ǫ √ n ≤ a ≤ (j + 1) 2 ǫ √ n ⇒ R(n, a) ≤ (2p(ǫ √ n)) j-2 p(n) δ • for j = 2, 3, ..., 2[ √ n/2] if ǫ < 1, • for j = 2, 3, ..., τ (n) with τ (n) = o( √ n) for every ǫ.
Remark 1: To obtain a similar conclusion, J. Dixmier [START_REF] Dixmier | Partitions avec sous-sommes interdites[END_REF] assumed that hypothesis (1) is true for ǫ √ n ≤ a ≤ 3ǫ √ n.

Proof: We shall prove Lemma 1 by induction on j. It is true for j = 2, 3 by (1). Let us suppose that j ≥ 4 and that the result is true up to j -1. Let a be such that j

2 ǫ √ n ≤ a ≤ (j+1) 2 ǫ √ n. Let Π ∈ R(n, a) and b = [ǫ √ n].
If b is not represented by Π, then Π belongs to a set E such that |E| ≤ p(n) δ .

If b is represented by Π, then we can write Π = (Π ′ , Π ′′ ), where S(Π ′ ) = b, S(Π ′′ ) = n -b and Π ′′ does not represent a -b. We get

a -b ≥ j 2 ǫ √ n -ǫ √ n = j -2 2 ǫ √ n ≥ ǫ √ n -b since j ≥ 4, and
a -b ≤ j + 1 2 ǫ √ n -ǫ √ n + 1 = j -1 2 ǫ √ n + 1.
Moreover we have

j 2 ǫ √ n -b ≥ j 2 ǫ √ n 1 - b n ≥ j 2 ǫ √ n -ǫ j 2 ǫ √ n √ n .
We still have to show (at least for n large enough)

j -1 2 ǫ √ n + 1 ≤ j 2 ǫ √ n - j 2 ǫ 2 .
• If ǫ < 1, since j/2 ≤ √ n/2, we have to check the inequality

-1/2ǫ √ n + 1 ≤ -ǫ 2 √ n/2,
which is true when n is large enough.

• In the second case, we want to show

-1/2ǫ √ n + 1 ≤ -1/2ǫ 2 τ (n) √ n .
This is true when n is large enough by using the hypothesis on τ (n).

We finally get

j 2 ǫ √ n -b ≥ a -b.
We deduce from the induction hypothesis that Π ′′ belongs to a set

F such that |F| ≤ (2p(ǫ √ n)) j-3 p(n) δ .
This implies that Π belongs to a set G such that

|G| ≤ p((ǫ √ n))(2p(ǫ √ n)) j-3 p(n) δ .
Hence we have

R(n, a) ≤ p(n) δ + p((ǫ √ n))(2p(ǫ √ n)) j-3 p(n) δ ≤ (2p(ǫ √ n)) j-2 p(n) δ
which completes the proof of the lemma.

Remark 2: It is easy to see that the result remains true when we replace all the R(n, a)'s by Q(n, a)'s or by Q(n, a, 2)'s, i.e. when we deal with partitions into unequal parts or with 2-reduced partitions (in the proof, if Π is into unequal parts, then Π ′ and Π ′′ are also into unequal parts; the same phenomenon occurs when we are dealing with 2-reduced partitions).

Applications

This lemma is useful to get upper bounds for p(n) and q(n) improving those obtained in [START_REF] Delglise | Sur les ensembles reprsents par les partitions d'un entier n[END_REF]. Lemma 1 allows us to prove the following lemma:

Lemma 2: When n → ∞ we have: 1. for 1.07 √ n ≤ a ≤ n -1.07 √ n, Q(n, a) ≤ exp((1 + o(1))1.732 √ n), 2. for 0.81 √ n ≤ a ≤ n -0.81 √ n, Q(n, a, 2) ≤ exp((1 + o(1))1.969 √ n).
To get Lemma 2 (the method is developped in [START_REF] Delglise | Sur les ensembles reprsents par les partitions d'un entier n[END_REF]), we find upper bounds for Q(n, a) and Q(n, a, 2) when a ranges over the interval [ǫ √ n, 2ǫ

√ n] and we choose the best ǫ; then we use Lemma 1 and the results in [START_REF] Erdös | On the number of partitions of n without a given subsum II, Analytic Number Theory[END_REF].

From Lemma 2, we get Theorem 2 as in [START_REF] Delglise | Sur les ensembles reprsents par les partitions d'un entier n[END_REF]. For instance, when studying q(n), we distinguish two cases according to whether the partition represents all integers between 1.07 √ n and n -1.07 √ n or not. We get this way

q(n) ≤ n exp((1 + o(1))1.732 √ n) + 2 1.07 √ n ≤ q(n) 0.955 since q(n) = exp((1 + o(1))π n/3) (cf. [4]).
The method is the same for p(n), since p(n) = q(n, 2) [1, Thorme 1].

Remark 3: The improvement on the exponents in the Theorem 2 is small (5.10 -3 ). This comes from the fact that the functions (cf. [START_REF] Delglise | Sur les ensembles reprsents par les partitions d'un entier n[END_REF]) we bound on an interval [x, 2x] (and not [x, 3x], see Remark 1) have slow variations around their minimum value. Indeed, even replacing [x, 2x] by [x, (1+η)x] with η decreasing to 0 would only lead to another small improvement (4.10 -3 less than our results). To make the exponents in the upper bounds really smaller, we need to find another method.