# Reconstruction of Convex Sets from One or Two X-rays

Yan Gerard*

Université Clermont Auvergne, LIMOS, France
yan.gerard@uca.fr

February 13, 2025

## Abstract

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 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 Di-rected 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 digital convex sets which are not fat remains an open question.

# 1 Introduction

## 1.1 About discrete tomography

In the mid 1990s, researchers in Material Science and especially in three dimen-sional Electron Microscopy previewed the development of an upcoming tech-nology able to count the number of atoms of a material crossed by a beam of straight lines [1]. According to the same strategy than Computerized Tomogra-phy, 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

<footnote>*Address for correspondence: Université Clermont Auvergne, LIMOS, France</footnote>

<footnote>†This work is supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005)</footnote>
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 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 [2, 3] for crys-
talline 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 [4, 5, 6]. 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.

1.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 \subset [0 \cdots m-1] \times
[0 \cdots 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) \in S | y = j\}|$
for $0 \le j \le n-1$ and $v_i(S) = |\{(x, y) \in S | x = i\}|$ for $0 \le i \le m-1$ (Fig. 1).

<figure><img src="image_1.png" /><figcaption>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, 1).</figcaption></figure>

It leads to introduce a generic problem of Discrete Tomography. The ques-
tion is the existence of a lattice set with given X-rays and belonging to a given
class $\mathcal{A}$ of lattice sets. We consider in this paper the problems of reconstruction
from one or two X-rays.

**Problem 1 (DT<sub>A</sub>(v)).** Given a class *A* of finite lattice sets,
*Input:* one vector *v* ∈ Z<sup>*m*</sup>.

**Output:** does there exist a lattice set $S \in \mathcal{A}$ included in the strip $[0 \cdots m-1] \times \mathbb{Z}$ with $V(S) = v$ ?
1.3 State of the art

It is known for a long time that for the whole class denoted $\mathcal{W}$ of all lattice sets,
the problem $DT_{\mathcal{W}}(h, v)$ can be solved in polynomial time by specific algorithms
[7, 8] or by min cut-max flow algorithms (Fig. 3).

<figure><img src="image_2.png" /><figcaption>Figure 3: Reduction of an instance of $DT_W(h, v)$ to a problem of flow.</figcaption></figure>

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 differ-
ent 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 $\mathcal{A} = \mathcal{P}$ of polyominoes [9]

• for the classes $\mathcal{A} = \mathcal{H}$ or $\mathcal{A} = \mathcal{V}$ of horizontally or vertically convex lattice sets [10].

• for the class $\mathcal{A} = \mathcal{H} \cap \mathcal{V}$ of HV-convex lattice sets (it is a particular case of puzzle games called *nonograms*) [9].

These NP-hardness results are however counter-balanced by two major results
of the field published in two seminal papers:

- The problem $DT_{H \cap V \cap P}(h, v)$ i.e the reconstruction of HV-convex polyominoes can be solved in polynomial time [10].

* Results of uniqueness have been obtained for the class $\mathcal{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 [11]. With the directions of X-rays providing uniqueness, these results have been completed by a polynomial time algorithm of reconstruction [12]. This algorithm follows the two steps used for the reconstruction of HV-convex polyominoes [10].
<table><caption>Table 1: Milestones results and neighboring open questions</caption><thead><tr><th>Class <i>A</i></th><th>Horizontal + vertical X-rays</th><th>4 directions or more</th></tr></thead><tbody><tr><td><i>H</i> ∩ <i>V</i> ∩ <i>P</i><br>(HV-convex polyominoes)</td><td><i>DT</i><sub><i>H</i>∩<i>V</i>∩<i>P</i></sub>(<i>h</i>, <i>v</i>)<br>polynomial time [13]</td><td>open</td></tr><tr><td><i>C</i><br>(Digital convex sets)</td><td><i>DT</i><sub><i>C</i></sub>(<i>h</i>, <i>v</i>)<br>open</td><td>polynomial time<br>(if uniqueness) [11, 12]</td></tr></tbody></table>

## 1.4 Three results

Our goal is to address the problem $DT_C(h, v)$. It is a twenty years old open question of Discrete Tomography [14, 15]. 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 presented in [10] 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:

**Theorem 1.1.** *The algorithm DAGTomo1 solves $DT_C(v)$ with a worst case time complexity in $O(m^{11} + m(\sum_{i=0}^{m-1} v_i)^5)$ where m is the number of columns of the X-ray and $\sum_{i=0}^{m-1} 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 1.2.** *Given a lattice set $S \subset \mathbb{Z}^2$, the South, West, North and East feet are*

$$ \text{South}(S) = \{(x, y) \in S | \forall (x', y') \in S, y' \ge y\}, $$

$$ \text{West}(S) = \{(x, y) \in S | \forall (x', y') \in S, x' \ge x\}, $$

$$ \text{North}(S) = \{(x, y) \in S | \forall (x', y') \in S, y' \le y\}, $$

$$ \text{East}(S) = \{(x, y) \in S | \forall (x', y') \in S, x' \le x\}. $$

*The lattice set $S$ is thin if there exists $(X, Y) \in \mathbb{Z}^2$ such that the feet are strictly*
<figure><img src="image_3.png" /><figcaption>Figure 4: **The four feet** of a lattice set $S$ are the subsets denoted South, West, North and East.</figcaption></figure>

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

<figure><img src="image_4.png" /><figcaption>Figure 5: **Thin VS fat lattice sets.** The fatness/thinness of an HV-convex lattice set depends on the relative positions of its feet. A lattice set is thin if there exists an integer point (X, Y) (represented by the green cross) strictly separating the pairs of feet in diagonally opposite quadrants. Otherwise it is fat.</figcaption></figure>

The class of the fat lattice sets (Fig. 5) is denoted $\mathcal{F}$. Then the class of the fat digital convex sets is $C \cap \mathcal{F}$. The last result of the paper is the following theorem:

**Theorem 1.2.** The algorithm DAGTomo2 solves $DT_{C \cap \mathcal{F}}(h, v)$ with a worst case time complexity in $O(m^7n^7)$.

The time complexity of DAGTomo2 is high but polynomial. The complexity of the reconstruction of the thin digital convex sets $DT_{C \setminus \mathcal{F}}(h, v)$ remains an open question.
## 1.5 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 1.2.

The third section proves Theorem 1.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 \cap \mathcal{F}}(h, v)$. It proves Theorem 1.2.

# 2 The structure of the bad guy counter-example

This section is focused on the reconstruction of HV-convex polyominos. It summarizes the results of the two previous episodes [10] and [16] by defining the *switching components* and provides a counter-example of a conjecture.

## 2.1 Episode 1: the reconstruction procedure with its filling/aggregation strategy

The milestone paper [10] proved that the problem $DT_{H \cap V \cap P}(h, v)$ can be solved in polynomial time. There exists an extensive literature around this problem [17, 18] and several algorithms have been derived from this algorithm [19, 12, 20, 21]. 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 $\text{Kernel}_0$. The algorithm tries several subsets $\text{Kernel}_0$ and for each, the algorithm repeats the reconstruction procedure.

**Choosing the Feet.** The first set of points $\text{Kernel}_0$ assumed to belong to the solution is not chosen randomly. The original strategy of [10] is to choose as set $\text{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^2n^2$ different initial kernels $\text{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 \cdots m-1] \times [0 \cdots n-1]$ in three sets denoted Kernel, Out, and Undetermined.

* The kernel $\text{Kernel}$ contains the integer points which are currently known to belong to all solutions (up to the considered subset $\text{Kernel}_0$).

* The set Out contains the integer points which are currently known to be excluded from all solutions.
<figure><img src="image_5.png" /><figcaption>Figure 6: The feet and the corners. The kernel is initialized by choosing the positions of the four feet North, South, East, and West. At each stage, the undetermined points are represented by small grey disks. The kernel points are represented by small black disks in grey cells. The excluded points are red disks in pink cells. After the filling step, the set of the undetermined points is 4-connected. It provides a partition of the undetermined points in 4 corners.</figcaption></figure>

* 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 $\leftarrow$ Kernel$_0$, Out $\leftarrow$ $\emptyset$ and Undetermined $\leftarrow$ $[0 \cdots m - 1] \times [0 \cdots n - 1] \setminus$ Kernel$_0$.

**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 [22, 12] 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.

We illustrate the filling step on the *bad guy* instance $DT_{H \cap V \cap P}(h_0, v_0)$ with

$$h_0 = (2, 4, 6, 7, 9, 8, 9, 9, 9, 7, 7, 8, 6, 5, 3, 1) \qquad (1)$$

and

$$v_0 = (1, 2, 7, 7, 10, 9, 11, 11, 9, 9, 9, 6, 6, 2, 1). \qquad (2)$$

The chosen position of the feet is South = $\{(10, 0), (11, 0)\}$, North = $\{(5, 15)\}$, East = $\{(0, 12)\}$ and West = $\{(14, 5)\}$ in Fig. 7.
<figure><img src="image_6.png" /><figcaption>Figure 7: **Filling step.** On the bad guy instance starting from a given position of the feet, we show the partition of the region of interest in Kernel $\cap$ Out $\cap$ Undetermined at different stages.</figcaption></figure>

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 [10] 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 $\cup$ NE $\cap$ SE $\cap$ 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 $\cup$ SE, then the point denoted $\bar{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 a horizontal East correspondent $|p = (i + h_j, j)$ (Fig. 8). Horizontal and vertical correspondences are symmetric relations.
<figure><img src="image_7.png" /><figcaption>**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.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 9: Switching components.** In each switching component, we represent the points alternatively by squares □ and diamonds ◊ to express that their Boolean variables are negation from each other. Either the squares, or the diamonds of a switching component are in a solution.</figcaption></figure>

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 2.1.** A switching component *P* is a cycle of corresponding undetermined points (Fig. 9).

**Aggregation Step.** It remains us to determine which undetermined points should 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 [10] 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 [23].

**Old Oral Conjecture.** 25 years after the seminal paper presenting this algorithm [10], 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.

## 2.2 Episode 2: structures of the switching components

Before going further, notice that the properties used for the reconstruction procedure of an HV-convex solution can also be used for the reconstruction of digital convex lattice sets since digital convexity implies HV-convexity.

According to [16], 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.

<figure><img src="image_9.png" /><figcaption>Figure 10: The six feasible configurations of the feet admitting HV-convex solutions [16]. 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.</figcaption></figure>

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
<figure><img src="image_10.png" /><figcaption>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 a 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.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>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 [16]. The list is now complete.</figcaption></figure>
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.

## 2.3 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><img src="image_12.png" /><figcaption>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.</figcaption></figure>
# 3 Reconstructing digital convex sets from a unique X-ray in polynomial time

We now consider the problem $DT_C(v)$ of the reconstruction of a digital convex lattice set from a unique vertical X-ray. It is a fundamental question which provides new tools for tackling the problem with horizontal and vertical X-rays.

In this section we provide a polynomial time algorithm called DAGtomo1 for solving $DT_C(v)$. We start by reducing the problem to a bounded region of interest. Then we provide a reduction of the problem to the research of a path in a DAG.

## 3.1 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_C(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 solutions of $DT_C(v)$ is invariant under vertical translations. It follows that if the instance $DT_C(v)$ admits a solution, then there is a solution with the origin as left bottom point. It allows us to reduce the problem $DT_C(v)$ to the research of a solution with the origin as left bottom point.

The second remark is that the vertical shearing $shear: x \leftarrow x, y \leftarrow y-x$ preserves the vertical X-ray, the convexity, and the vertical line $x = 0$. Then the set of the solutions of the instance $DT_C(v)$ is invariant by the vertical shear transform. It follows that if $DT_C(v)$ admits a solution $S$, then it admits a solution $S'$ with the same left bottom point than $S$ and such that the $y$ coordinate of the right bottom point of $S'$ is in the interval $[0, m-1]$ (we recall here that the $x$ coordinate of the right bottom points is $m-1$).

With these two remarks, we restrict the research of a solution of $DT_C(v)$ to a digital convex lattice set with the origin as left bottom point and a right bottom point of coordinates $(m-1, y_{m-1})$ with $0 \le y_{m-1} < m-1$.

It follows that the points of the segment joining the two extreme bottom points are included in the triangle $T_m$ of vertices $(0,0)$, $(m-1,0)$, and $(m-1, m-1)$ (Fig. 15). This triangle $T_m$ contains $\frac{m(m+1)}{2}$ integer points.

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_C(v)$, then its vertical distance to the triangle $T_m$ is at most $v_i - 1$. Otherwise the solution would not be convex. The region whose points $(i, y)$ are at vertical distance at most $v_i$ from $T_m$ is denoted $R_v$. It contains at most $\frac{m(m+1)}{2} + 2 \sum_{i=0}^{m-1} v_i - 2m$ points where $\sum_{i=0}^{m-1} v_i$ is the prescribed number of points of any solution. We have shown that if $DT_C(v)$ admits a solution, then there exists a solution included in $R_v$. The algorithm DAGtomo1 searches for a solution in this region.
<figure><img src="image_13.png" /><figcaption>Figure 14: **Region of work.** We fix the left bottom point at the origin. Then with vertical shearing, we can assume without loss of generality that the right bottom point $(m-1, y_{m-1})$ belongs to the vertical segment from $(m-1, 0)$ to $(m-1, m-2)$. We notice that the segment from the origin to $(m-1, y_{m-1})$ is by definition included in the convex hull of the solution and in the triangle $T_m$ of vertices $(0, 0)$, $(m-1, 0)$, $(m-1, m-1)$. By taking into account the vertical X-ray $v$, it provides a bounded region $R_v$ containing a solution if there exists one.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 15: **Quads.** The nodes of the DAG are quads (colored in pink). The common columns of $s$ and $\bar{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.</figcaption></figure>

## 3.2 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 $\Gamma(v)$ whose nodes are convex quads with the prescribed vertical X-ray and linked by edges if they have a convex junction (Fig. 15 and Fig. 16). To be more precise,

* the nodes of $\Gamma(v)$ are quads made by a pair of non vertical segments $s, \bar{s}$ in the following configuration.
<figure><img src="image_15.png" /><figcaption>Figure 16: **Oriented edges in the DAG.** There is an edge between a pair of consecutive quads if they share a segment and provide a strictly convex turn on the other side. The right quad is colored in red if it is not a successor of the left quad and in green if they are both linked by an edge in the DAG.</figcaption></figure>

1. First, the four vertices of the two segments $s$ and $\bar{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_v$.

2. We denote $[a \cdots b]$ the interval of the common $x$-coordinates of the two segments $s, \bar{s}$. We assume that the integral interval $[a..b]$ is not empty. Otherwise, the pair of segments $s, \bar{s}$ is excluded from the nodes.

3. The last condition is that the segment $\bar{s}$ is above the segment $s$ with the prescribed X-ray. By denoting $\bar{y}(i)$ the $y$ coordinate of the point of $\bar{s}$ of $x$ coordinate $i$ and $y(i)$ the $y$ coordinate of the point of $s$ of $x$ coordinate $i$, we request $[\bar{y}(i)] - [y(i)] = h_i$. In other words, the quad made by the convex hull of $s, \bar{s}$ must contain the prescribed number of points for each column with $x$ in $[a..b]$.

* We consider two nodes $s_1, \bar{s}_1$ and $s_2, \bar{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, \bar{s}_1$ (respectively $s_2, \bar{s}_2$). The DAG $\Gamma(v)$ has an oriented edge from $s_1, \bar{s}_1$ to $s_2, \bar{s}_2$ if

1. they have a common segment: either $s_1 = s_2$ or $\bar{s}_1 = \bar{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.

The set Left contains the quads with the origin as vertex. If the first coordinate of the X-ray $v$ is $v_0 = 1$, then the quads $s, \bar{s}$ of Left are only triangles with the origin as left vertex of $s$ and $\bar{s}$. Otherwise the two segments $s, \bar{s}$ of the quads in Left have respectively $(0, 0)$ and $(0, v_0)$ as left nodes.

The set Right contains the quads with at least one vertex of $x$ coordinate $m-1$. If the last coordinate of the X-ray $v$ is $v_{m-1} = 1$, then the quads $s, \bar{s}$
of Right are only triangles with the right vertex of coordinates $x = m - 1$ and
$0 \le y \le m - 1$. Otherwise, the quads $s, \bar{s}$ of Right have a vertical edge between
two vertices $(m - 1, y_r)$ with $0 \le y_r \le m - 1$ and the point of coordinates
$(m - 1, y_r + v_{m-1} - 1)$.

**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 $\Gamma(v)$ (Fig. 17).

<figure><img src="image_16.png" /><figcaption>Figure 17: **From a solution to a path in the DAG and conversely.** We reduce the problem of finding a solution of $DT_C(v)$ to the research of a path from Left to Right in the DAG $\Gamma(v)$.</figcaption></figure>

**Proposition 3.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 $\Gamma(v)$.

*Proof.* By construction, if there exists a path in the DAG $\Gamma(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$. $\square$

**Algorithm.** The algorithm DAGTomo1 builds a part of the DAG $\Gamma(v)$ and searches for a path from Left to Right.

The graph $\Gamma(v)$ contains at most $k^4$ nodes/quads where $k$ is cardinality of the
region $R_v$. Each node has at most $2k$ edges since one of the left nodes is replaced
by another point of $R_v$. There is no interest in computing the whole graph $\Gamma(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) \le mk$. It provides a worst-case time complexity in $O(mk^5)$. We have already bounded $k$ by $\frac{m(m+1)}{2} + 2\sum_{i=0}^{m-1} v_i - 2m$. With the inequality $(a+b)^n \le (2a)^n + (2b)^n = 2^n(a^n + b^n)$ for positive $a$ and $b$, the property that $k$ is $O(m^2 + \sum_{i=0}^{m-1} v_i)$ implies that $k^5$ is $O(m^{10} + (\sum_{i=0}^{m-1} v_i)^5)$. It shows that the complexity of DAGTomo1 is $O(m^{11} + m(\sum_{i=0}^{m-1} v_i)^5)$ and proves Theorem 1.1.

# 4 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 1.2.

The algorithm DAGTomo2 uses a two-step reconstruction procedure as pre-
sented 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 strat-
egy as in Section 3. This main new step is presented in section 4.3.

4.1 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 \cdots m-1] \times [0 \cdots n-1] = \text{Kernel} \cup \text{Out} \cup \text{Undetermined}$. The kernel
is initialized by choosing a position of the feet: Kernel $\leftarrow$ South $\cup$ West $\cup$ North $\cup$
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.

4.2 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 $\leftarrow 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 $\leftarrow 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 [24]). By repeating this operation at most $mn$ time, the total time taken by this filling

<figure><img src="image_17.png" /><figcaption>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 $\leftarrow conv_{Z^2}(Kernel)$. It provides directly a partition of the undetermined points in four subsets NW, NE, SE and SW.</figcaption></figure>
operation is bounded by $O(m^2n^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\} \cap \text{Out}$. If $x$ is in $\{y\} \cap \text{Out}$, then $y$ is excluded and added to Out. For each point $x$ and each suspected point $y \in \text{Undetermined}$, the computation of the convex hull of $\{y\} \cap \text{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^2n^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 \cdots a], ]a \cdots b[, [b \cdots c], ]c \cdots d[ \text{ and } [d \cdots m-1] \text{ (some of them can be empty). The two segments with points of $x$-coordinates in } [0 \cdots a] \text{ and } [d \cdots m-1] \text{ contain the left and right excluded points. The central segment } [b \cdots c] \text{ contains the kernel points while the two intermediate intervals } ]a \cdots b[ \text{ and } ]c \cdots d[ \text{ 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 :

* if $a < c - h_j - 1$ then $a \leftarrow c - h_j - 1$

* if $b > d - h_j$ then $b \leftarrow d - h_j$,

* if $c < a + h_j$ then $c \leftarrow a + h_j$,

* if $d > b + h_j$ then $d \leftarrow b + h_j$

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.

## 4.3 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 \cap \mathcal{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 \cap 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><img src="image_18.png" /></figure>

**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 \cap NEV$, $SW' = SW \cap SWV$, and $SE' = SE \cap 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 10[16], 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.

<figure><img src="image_19.png" /><figcaption>Figure 20: **The region to fix.** In the case of feet in a fat position, the four undetermined borders belong to four regions on different sides of the horizontal strip Hstrip represented in brown and the vertical strip Vstrip represented in blue. The problem of reconstruction can be reduced to the computation of the polygonal lines cutting the four undetermined regions represented in white.</figcaption></figure>

**The DAG.** We introduce the Directed Acyclic Graph $\Gamma(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 $\Gamma(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 guarantees that the X-ray of the solution fits with the prescribed X-rays $h$ and $v$. We first associate to each segment $s_{\text{NW}}$, $s_{\text{NE}}$, $s_{\text{SW}}$, $s_{\text{SE}}$ the set of consecutive rows and columns that it involves. For a segment $s$, these two sets are denoted $\text{rows}(s)$ and $\text{columns}(s)$. The sets $\text{rows}(s)$ and $\text{columns}(s)$ first contain the consecutive integer rows and columns crossed by $s$ (Fig. 21). If the segment $s_{\text{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 $\text{columns}(s_{\text{NW}})$ with its left columns. We proceed in the same way with the vertical strip. If the segment $s_{\text{NW}} = xy$ has one vertex $y$ in the vertical strip Vstrip, then we complete $\text{rows}(s_{\text{NW}})$ with the rows above it. By symmetry and rotations, we extend in the same manner the six other sets $\text{rows}(s_{\text{NE}})$, $\text{columns}(s_{\text{NE}})$, $\text{rows}(s_{\text{SE}})$, $\text{columns}(s_{\text{SE}})$, $\text{rows}(s_{\text{SW}})$, $\text{columns}(s_{\text{SW}})$.
Once the rows and columns associated to each segment are defined, we can go to the octagon. Each octagon is determined by its four segments $s_{\text{NW}}$, $s_{\text{NE}}$, $s_{\text{SW}}$, $s_{\text{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 $\text{NorthRows}(q) = \text{rows}(s_{\text{NW}}) \cap \text{rows}(s_{\text{NE}})$ and $\text{SouthRows}(q) = \text{rows}(s_{\text{SW}}) \cap \text{rows}(s_{\text{SE}})$ and in the

<figure><img src="image_20.png" /><figcaption>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_{\text{NW}}$. In the images 4, 5, 6 the rows of $\text{rows}(d)$, $\text{rows}(e)$ and $\text{rows}(f)$ and the columns of $\text{columns}(d)$, $\text{columns}(e)$ and $\text{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.</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>Figure 22: **An octagon/node of $\Gamma(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 *NorthRows*($q$), *SouthRows*($q$) and the columns *WestColumn*($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).</figcaption></figure>

columns in *WestColumn*($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
*NorthRows*($q$),
*SouthRows*($q$) and columns *WestColumn*($q$), *RightColumn*($q$) must
be non 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.

* 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 sense 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).

<figure><img src="image_22.png" /><figcaption>Figure 23: **Start and End octagons.** On the left, an octagon is in Start if the four segments $s_{\text{NW}}$, $s_{\text{NE}}$, $s_{\text{SW}}$ and $s_{\text{SE}}$ have a vertex in the horizontal strip (colored in dark grey) and another vertex outside. On the right, an octagon is in End if the four segments $s_{\text{NW}}$, $s_{\text{NE}}$, $s_{\text{SW}}$ and $s_{\text{SE}}$ have a vertex in the vertical strip (colored in dark grey) and another vertex outside. Notice that the octagon in Start is degenerated because the south segments have a common vertex. This degenerated case might arise when a foot contains a unique point.</figcaption></figure>

* Start is the set of nodes/octagons with the property that the four segments $s_{\text{NW}}$, $s_{\text{NE}}$, $s_{\text{SW}}$ and $s_{\text{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_{\text{NW}}$, $s_{\text{NE}}$, $s_{\text{SW}}$ and $s_{\text{SE}}$ have one vertex in the vertical strip Vstrip and the other vertex outside.

Notice the special configurations of the rows *NorthRows*(q), *SouthRows*(q) and columns *WestColumn*(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 *NorthRows*(q), *SouthRows*(q) and columns *WestColumn*(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 \cap \mathcal{F}}(h, v)$ to the research of a path going from Start to End in the graph $\Gamma(h, v)$.

**Proposition 4.1.** The problem $DT_{C \cap \mathcal{F}}(h, v)$ with some considered positions of the feet South, West, North and East admits a solution if and only if after the filling step, there exists a path from Start to End in the graph $\Gamma(h, v)$.

*Proof.* We prove Proposition 4.1 by showing first that if $DT_{C \cap \mathcal{F}}(h, v)$ admits a solution, then there is a path from Start to End in the graph $\Gamma(h, v)$ and
secondly by stating that the existence of a path from Start to End provides a
solution of $DT_{C \cap \mathcal{F}}(h, v)$.

We first assume first that $DT_{C \cap \mathcal{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 [16], 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 \le i \le 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.

<figure><img src="image_23.png" /><figcaption>Figure 24: From a solution to a path in $\Gamma(h, v)$.</figcaption></figure>

Conversely, we assume that we have a path of consecutive octagons $(q_i)_{1 \le i \le k}$
in $\Gamma(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 = \bigcup_{0 \le i \le k} q_i \cup \text{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<sub>Z<sup>2</sup></sub>(Kernel). The set ⋃<sub>0≤i≤k</sub> q<sub>i</sub> 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 ⋃<sub>0≤i≤k</sub> q<sub>i</sub>. 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$ guar-
antees the X-rays for the rows NorthRows($q_i$), SouthRows($q_i$) and columns
WestColumn($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 rows and columns
which are not in the already determined strips Hstrip and Vstrip.
□

**DAGTomo2 Aggregation Algorithm.** The DAGTomo2 aggregation algorithm is based on Proposition 4.1 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 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⁴n⁴). 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⁴n⁴) quadruplets of segments sNW, sNE, sSE, sSW.
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 $\Gamma(h, v)$ takes $O((m+n)m^4n^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 \cup q'$ and
whether $q'$ is a vertex of $\Gamma(h, v)$. It takes a constant time.
## 4.4 Analysis

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

The reconstruction procedure starts with the filling step. The total time of the new filling operations related to the digital convexity is $O(m^2n^2 \log(m+n))$. The total time of the other filling operations is $O(mn)$. It provides a bound $O(m^2n^2 \log(m+n))$ for the filling step.

The reconstruction procedure ends with the aggregation step. The time complexity of the Depth first search for a given graph is $O(|V| + |E|)$ where $|V|$ is the total number of vertices and $|E|$ the total number of edges of the graph $\Gamma(h, v)$. The complexity of the algorithm is not affected by the computation on the fly of the edges since it is done in constant time. As we have $|V| = O(m^4n^4)$ and at most $O(mn)$ neighbors per vertex, we have $|V| = O(m^5n^5)$. By repeating the reconstruction procedure at most $m^2n^2$ times, the complexity of DAGTomo2 is $O(m^7n^7)$. It proves Theorem 1.2.

## Perspectives

We have shown that the DAG strategy used in the algorithms DAGTomo2 and DAGTomo2 allows us to solve $DT_C(v)$ and $DT_{C \cap \mathcal{F}}(h, v)$ in polynomial time. It is a step beyond the previously known results. Can it be used to fully solve the challenging problem $DT_C(h, v)$ or at least some other configurations of the feet than the fat configuration f) of Fig. 12? The complexity of the reconstruction of digital convex lattice sets from a pair of X-rays remains an open question but there is still hope that new results can be derived from the ideas presented in this paper or from other breakthroughs.

## References

[1] Carazo JM, Sorzano CO, Rietzel E, Schröder R, Marabini R. Discrete Tomography in Electron Microscopy, pp. 405–416. Birkhäuser Boston, Boston, MA. ISBN 978-1-4612-1568-4, 1999. doi:10.1007/978-1-4612-1568-4_18.

[2] Batenburg K, Bals S, Sijbers J, Kübel C, Midgley P, Hernandez J, Kaiser U, Encina E, Coronado E, van Tendeloo G. 3D imaging of nanomaterials by discrete tomography. *Ultramicroscopy*, 2009. **109**:730–40. doi:10.1016/j.ultramic.2009.01.009. 43.01.05; LK 01.

[3] Van Aert S, Batenburg KJ, Rossell MD, Erni R, Van Tendeloo G. Three-dimensional atomic imaging of crystalline nanoparticles. *Nature*, 2011. **470**:374–377. doi:10.1038/nature09741.

[4] Gardner RJ. Geometric Tomography. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1995.

[5] Herman GT, Kuba A. Discrete Tomography - Foundations, Algorithms and Applications. Birkhauser, 1999. ISBN-0817636145.
[6] Herman GT, Kuba A. Advances in Discrete Tomography and Its Applications. Birkhauser, 2007. ISBN-0817636145.

[7] Gale D. A theorem on flows in networks. Pacific J. Math., 1957. 7:1073-1082. doi:doi:10.2140/pjm.1957.7.1073.

[8] Ryser H. Combinatorial properties of matrices of zeros and ones. Can. J. Math., 1957. 9:371-377.

[9] Woeginger GJ. The reconstruction of polyominoes from their orthogonal projections. Information Processing Letters, 2001. 77(5):225-229. doi:https://doi.org/10.1016/S0020-0190(00)00162-9. URL http://www.sciencedirect.com/science/article/pii/S0020019000001629.

[10] Barcucci E, Lungo AD, Nivat M, Pinzani R. Reconstructing Convex Polyominoes from Horizontal and Vertical Projections. Theor. Comput. Sci., 1996. 155(2):321-347. doi:10.1016/0304-3975(94)00293-2. URL https://doi.org/10.1016/0304-3975(94)00293-2.

[11] Gardner R, Gritzmann P. Determination of finite sets by X-rays. Transactions of the American Mathematical Society, 1997. 349(6):2271-2295.

[12] Brunetti S, Daurat A. Reconstruction of convex lattice sets from tomographic projections in quartic time. Theoretical Computer Science, 2008. 406(1):55-62. doi:https://doi.org/10.1016/j.tcs.2008.06.003. Discrete Tomography and Digital Geometry: In memory of Attila Kuba.

[13] Barcucci E, Dulio P, Frosini A, Rinaldi S. Ambiguity Results in the Characterization of hv-convex Polyominoes from Projections. In: Discrete Geometry for Computer Imagery - 20th IAPR International Conference, DGCI 2017, Vienna, Austria, September 19-21, 2017, Proceedings. 2017 pp. 147-158. doi:10.1007/978-3-319-66272-5_13.

[14] Dulio P, Frosini A, Rinaldi S, Tarsissi L, Vuillon L. First Steps in the Algorithmic Reconstruction of Digital Convex Sets. In: Brlek S, Dolce F, Reutenauer C, Vandomme É (eds.), Combinatorics on Words - 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11-15, 2017, Proceedings, volume 10432 of Lecture Notes in Computer Science. Springer, 2017 pp. 164-176. doi:10.1007/978-3-319-66396-8_16.

[15] Marco ND, Frosini A. Properties of SAT Formulas Characterizing Convex Sets with Given Projections. In: Baudrier É, Naegel B, Krähenbühl A, Tajine M (eds.), Discrete Geometry and Mathematical Morphology - Second International Joint Conference, Strasbourg, France, October 24-27, 2022, Proceedings, volume 13493 of Lecture Notes in Computer Science. Springer, 2022 pp. 153-166. doi:10.1007/978-3-031-19897-7_13.

[16] Gerard Y. Regular switching components. Theororetical Computer Science, 2019. 777:338-355. doi:10.1016/j.tcs.2019.01.010.

[17] Dulio P, Frosini A. Characterization of hv-Convex Sequences. J. Math. Imaging Vis., 2022. 64(7):771-785. doi:10.1007/s10851-022-01093-z.
[18] Dulio P, Frosini A. On Some Geometric Aspects of the Class of hv-Convex Switching Components. In: Lindblad J, Malmberg F, Sladoje N (eds.), Discrete Geometry and Mathematical Morphology - First International Joint Conference, DGMM 2021, Uppsala, Sweden, May 24-27, 2021, Proceedings, volume 12708 of Lecture Notes in Computer Science. Springer, 2021 pp. 299-311. doi:10.1007/978-3-030-76657-3_21.

[19] Dulio P, Frosini A, Rinaldi S, Tarsissi L, Vuillon L. Further steps on the reconstruction of convex polyominoes from orthogonal projections. J. Comb. Optim., 2022. 44(4):2423-2442. doi:10.1007/s10878-021-00751-z.

[20] Frosini A, Vuillon L. Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses. Theor. Comput. Sci., 2019. 777:329-337. doi: 10.1016/j.tcs.2019.01.001.

[21] Brunetti S, Daurat A. Reconstruction of convex lattice sets from tomographic projections in quartic time. Theor. Comput. Sci., 2008. 406(1-2):55-62. doi:10.1016/j.tcs.2008.06.003.

[22] Brunetti S, Daurat A, Kuba A. Fast Filling Operations Used in the Reconstruction of Convex Lattice Sets. In: Kuba A, Nyúl LG, Palágyi K (eds.), Discrete Geometry for Computer Imagery. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006 pp. 98-109. doi:10.1007/119073509.

[23] Aspvall B, Plass MF, Tarjan RE. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Inf. Process. Lett., 1979. 8:121-123. doi:10.1016/0020-0190(79)90002-4.

[24] Brodal G, Jacob R. Dynamic planar convex hull. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002 pp. 617-626. doi:10.1109/SFCS.2002.1181985.