pith. sign in

arxiv: 2211.08091 · v4 · submitted 2022-11-15 · 💻 cs.CG

Reconstruction of Convex Sets from One or Two X-rays

Yan Gerard This is my paper

Pith reviewed 2026-05-24 10:24 UTC · model grok-4.3

classification 💻 cs.CG
keywords discrete tomographyconvex lattice setsX-ray reconstructionpolynomial time algorithmdirected acyclic graphHV-convex polyominoesfat convex sets
0
0 comments X

The pith

Reconstruction of convex lattice sets from one X-ray runs in polynomial time by encoding convex aggregation as a DAG path search.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the convex aggregation problem for digital convex lattice sets reduces to finding paths in a directed acyclic graph, which solves the single-X-ray reconstruction task in polynomial time. The same modeling approach extends to fat convex sets, where two X-rays also permit polynomial-time reconstruction. This follows after showing that the usual two-step method for HV-convex polyominoes fails in general, as demonstrated by an explicit counterexample called the bad guy that disproves a prior conjecture. The complexity for non-fat sets with two X-rays is left open.

Core claim

The reconstruction of a digital convex lattice set from only one X-ray can be performed in polynomial time. We prove it by encoding the convex aggregation problem in a Directed Acyclic Graph. With the same strategy, we prove that the reconstruction of fat digital convex sets from their horizontal and vertical X-rays can be solved in polynomial time. Fatness is a property of the digital convex sets regarding the relative position of the left, right, top and bottom points of the set. The complexity of the reconstruction of the lattice sets which are not fat remains an open question.

What carries the argument

Encoding the convex aggregation step as a search for a path in a suitably constructed Directed Acyclic Graph, where each path corresponds to a valid filling that respects the X-ray projections.

If this is right

  • The standard convex aggregation step for HV-convex polyominoes does not always yield a solution, as shown by the bad guy counterexample.
  • Single-X-ray reconstruction of any digital convex lattice set is polynomial-time solvable.
  • Two-X-ray reconstruction of fat digital convex lattice sets is polynomial-time solvable.
  • The complexity status for two-X-ray reconstruction of non-fat convex lattice sets is left unresolved.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Fatness appears to be the precise property that removes the combinatorial obstructions illustrated by the bad guy, suggesting it may be the boundary between tractable and intractable cases.
  • If the general two-X-ray problem turns out to be NP-hard, the DAG technique could still serve as a practical heuristic or approximation for near-fat instances.
  • The DAG encoding might generalize to other projection directions or to higher-dimensional lattice sets if analogous acyclicity can be maintained.

Load-bearing premise

That every valid convex aggregation of the lattice points corresponds exactly to the existence of a path in the defined DAG, with no hidden constraints that would make the search fail to capture all solutions or introduce NP-hardness.

What would settle it

An explicit family of convex lattice sets for which the DAG constructed from the X-rays either admits a path that produces an invalid set or misses a valid reconstruction, causing the algorithm to output an incorrect answer or run in superpolynomial time.

Figures

Figures reproduced from arXiv: 2211.08091 by Yan Gerard.

Figure 1
Figure 1. Figure 1: The horizontal and vertical X-rays of the lattice set S are the vectors V (S) = (1, 2, 4, 5, 3, 1) and H(S) = (2, 4, 4, 5, 1). With a vertical and a horizontal X-ray instead of just a vertical X-ray, we have the following problem: Problem 2. (DTA(h, v)) Given a class A of finite lattice sets, Input: two vectors h ∈ Z n and v ∈ Z m. Output: does there exist a lattice set S ∈ A included in the rectangle [0 ·… view at source ↗
Figure 2
Figure 2. Figure 2: Main classes of convex lattice sets. The set S1 is not a polyomino since not connected. The set S2 is not horizontally convex, S3 is not vertically convex. The set S4 is connected, horizontally and vertically convex. It is an HV-convex polyomino and then belongs to the class H ∩ V ∩ P. The set S5 is not digital convex while S6 is digital convex (S6 ∈ C) [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Reduction of an instance of DTW(h, v) to a problem of flow. Many variants of the problem DTW(h, v) have been investigated, not only with horizontal and vertical X-rays but in different dimensions, with different directions of X-rays and different kinds of [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The four feet of a lattice set S are the subsets denoted South, West, North and East. Definition 1.3. Given a lattice set S ⊂ Z 2 , the South, West, North and East feet are South(S) = {(x, y) ∈ S|∀(x ′ , y′ ) ∈ S, y′ ≥ y}, West(S) = {(x, y) ∈ S|∀(x ′ , y′ ) ∈ S, x′ ≥ x}, North(S) = {(x, y) ∈ S|∀(x ′ , y′ ) ∈ S, y′ ≤ y}, East(S) = {(x, y) ∈ S|∀(x ′ , y′ ) ∈ S, x′ ≤ x}. The lattice set S is thin if there exi… view at source ↗
Figure 5
Figure 5. 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. The time complexity of DAGTomo2 is high but polynomial. The complexity of the reconstruction of th… view at source ↗
Figure 6
Figure 6. 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 … view at source ↗
Figure 7
Figure 7. 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 ∩ Out ∩ Undetermined at different stages. Then we have a partition of the undetermined points in Undetermined = NW ∪ NE ∩ SE ∩ SW. We can build another partition in the following way. The starting remark is that an undetermined point cannot be isolated in a row or a co… view at source ↗
Figure 8
Figure 8. Figure 8: Corresponding points and switching components. After the filling step, horizontal correspon￾dences 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 [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. 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. are the negation from each other. We represent graphically this relation by denoting the points either with a square □ or with a diamond ♢. If… view at source ↗
Figure 10
Figure 10. 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. For each one of the six configurations, the set of undetermined points is restricted to a … view at source ↗
Figure 11
Figure 11. 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 oriente… view at source ↗
Figure 12
Figure 12. Figure 12: The fundamental cycles of the switching components in each configuration (except the configu￾ration 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 [PITH_FULL_IMAGE:figures/full_fig_p013_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Counter-example of the conjecture. The filling operations lead to a unique switching compo￾nent. 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 [PITH_FULL_IMAGE:figures/full_fig_p014_13.png] view at source ↗
Figure 14
Figure 14. 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, ym−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, ym−1) is by definition included in the convex hull of the solution and in the triangle Tm of vertices (0, 0), (m − 1, 0), (… view at source ↗
Figure 15
Figure 15. Figure 15: Quads. The nodes of the DAG are quads (colored in pink). The common columns of s and s are highlighted in blue. For each one of these columns, the number of points of the quad is equal to the prescribed value given by the vertical X-ray. 3.2. DAGTomo1 We present now the algorithm DAGtomo1 which solves DTC(v) by searching for a solution in the region Rv. The strategy is to reduce the problem to the search … view at source ↗
Figure 16
Figure 16. 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. The DAG. We consider the following Directed Acyclic Graph Γ(v) whose nodes are convex quads with the prescribed ver… view at source ↗
Figure 17
Figure 17. Figure 17: From a solution to a path in the DAG and conversely. We reduce the problem of finding a solution of DTC(v) to the research of a path from Left to Right in the DAG Γ(v). Proposition 3.1. The problem DTC(v) admits a solution if and only if there exists a path going from Left to Right in the DAG Γ(v). Proof: By construction, if there exists a path in the DAG Γ(v), we consider the solution S obtained by union… view at source ↗
Figure 18
Figure 18. 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 ← convZ2 (Kernel). It provides … view at source ↗
Figure 19
Figure 19. 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… view at source ↗
Figure 20
Figure 20. 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 [PITH_FULL_IMAGE:figures/ful… view at source ↗
Figure 21
Figure 21. 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 sNW. In the … view at source ↗
Figure 22
Figure 22. Figure 22: An octagon/node of Γ(h, v). The octagon q is defined by its four non degenerated seg￾ments sNW, sNE, sSW, sSE whose vertices are chosen respectively in NW′ , NE′ , SW′ and SE′ (the or￾ange/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 W estColumn(q), RightColumn(q) are non empty and that for each one of the rows and c… view at source ↗
Figure 23
Figure 23. Figure 23: Start and End octagons. On the left, an octagon is in Start if the four segments sNW, sNE, sSW and sSE 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 sNW, sNE, sSW and sSE have a vertex in the vertical strip (colored in dark grey) and another vertex outside. Notice that the octagon in Start is degenerated bec… view at source ↗
Figure 24
Figure 24. Figure 24: From a solution to a path in Γ(h, v). 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 qi guar￾antees the X-rays for the rows NorthRows(qi), SouthRows(qi) and col… view at source ↗
read the original 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 \textit{the bad guy} and disproves a conjecture of the domain. (2) The reconstruction of a digital convex lattice set from only one X-ray can be performed in polynomial time. We prove it by encoding the convex aggregation problem in a Directed Acyclic Graph. (3) With the same strategy, we prove that the reconstruction of fat digital convex sets from their horizontal and vertical X-rays can be solved in polynomial time. Fatness is a property of the digital convex sets regarding the relative position of the left, right, top and bottom points of the set. The complexity of the reconstruction of the lattice sets which are not fat remains an open question.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript addresses reconstruction of convex lattice sets from horizontal and/or vertical X-rays in discrete tomography. It exhibits a counterexample ('the bad guy') demonstrating that the standard convex aggregation step for HV-convex polyominoes fails to always produce a solution, thereby disproving a conjecture. It further claims that reconstruction of a digital convex lattice set from a single X-ray is solvable in polynomial time via reduction of the convex aggregation problem to a path search in a suitably constructed DAG, and that the same strategy yields a polynomial-time algorithm for fat digital convex sets from two X-rays, where fatness is defined in terms of the relative positions of the leftmost, rightmost, topmost, and bottommost points.

Significance. If the DAG constructions are verified to be of polynomial size, to enforce all required convexity and switching-component constraints without omissions or extraneous solutions, and to correctly handle the fatness restriction, the results would establish efficient algorithms for the one-X-ray case and the fat two-X-ray case. The explicit counterexample is a concrete contribution that settles a prior conjecture negatively. The decision to leave the complexity status of non-fat two-X-ray instances open is appropriate.

major comments (2)
  1. [DAG encoding for one-X-ray case] The reduction of convex aggregation to a DAG path problem (central to both polynomial-time claims) requires an explicit argument that every path in the constructed DAG corresponds to a valid convex aggregation and that every valid aggregation arises from some path; this must be shown to hold without hidden constraints that could render the search NP-hard in practice.
  2. [fat digital convex sets and two-X-ray reconstruction] For the two-X-ray fat case, the manuscript must demonstrate that the fatness condition precisely excludes all configurations (such as the bad-guy example) in which the two-X-ray aggregation problem may fail or become intractable, and that the DAG construction remains complete for every fat instance.
minor comments (3)
  1. The abstract contains a minor grammatical issue ('yielding to this result' should read 'leading to this result').
  2. [Definition of fatness] The definition of fatness should be stated with greater formality, ideally via explicit inequalities or coordinate conditions on the extremal points, to facilitate verification that it excludes exactly the problematic cases.
  3. Figure or pseudocode illustrating the DAG construction (vertices, edges, and weights) would improve readability of the algorithmic claims.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive recommendation for minor revision, and the recognition that the counterexample settles the conjecture negatively while leaving the non-fat two-X-ray case open. We address the two major comments below and will incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [DAG encoding for one-X-ray case] The reduction of convex aggregation to a DAG path problem (central to both polynomial-time claims) requires an explicit argument that every path in the constructed DAG corresponds to a valid convex aggregation and that every valid aggregation arises from some path; this must be shown to hold without hidden constraints that could render the search NP-hard in practice.

    Authors: We agree that an explicit bijection argument is needed. The manuscript describes the DAG construction that encodes the convex aggregation problem and states that a path search solves it in polynomial time, but does not contain a self-contained proof that every path yields a valid aggregation satisfying all convexity and switching-component constraints and that every valid aggregation corresponds to a path. In the revision we will add a dedicated subsection proving this equivalence, confirming that the DAG size remains polynomial and that the reduction introduces no hidden constraints that would affect membership in P. revision: yes

  2. Referee: [fat digital convex sets and two-X-ray reconstruction] For the two-X-ray fat case, the manuscript must demonstrate that the fatness condition precisely excludes all configurations (such as the bad-guy example) in which the two-X-ray aggregation problem may fail or become intractable, and that the DAG construction remains complete for every fat instance.

    Authors: We will revise the manuscript to include an explicit verification that the bad-guy example violates the fatness condition (specifically, the relative positions of its extremal points). We will also add an argument showing that fatness eliminates precisely the configurations where aggregation can fail or become intractable, and that the same DAG construction remains complete and correct for every fat instance, with no omissions of valid solutions. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central claims reduce the reconstruction problems to existence of a path in an explicitly constructed DAG whose nodes and edges encode the convexity and switching-component constraints. This is a direct algorithmic reduction to a standard problem (DAG reachability) whose polynomial-time complexity is established independently of the paper. No self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The definition of fatness is an explicit restriction that excludes the exhibited counterexample, not a circular assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no free parameters or invented entities. It relies on the standard fact that path existence in DAGs is polynomial-time solvable and on the domain-specific definition of fat digital convex sets.

axioms (1)
  • standard math Path search or existence in a directed acyclic graph is solvable in polynomial time
    Invoked to conclude that the encoded reconstruction problem is polynomial-time solvable.

pith-pipeline@v0.9.0 · 5755 in / 1191 out tokens · 29064 ms · 2026-05-24T10:24:32.848499+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Discrete tomography: Foundations, a lgorithms, and applications

    Carazo JM, Sorzano CO, Rietzel E, Schr ¨oder R, Marabini R. Discrete Tomography in Electron Mi- croscopy, pp. 405–416. Birkh ¨auser Boston, Boston, MA. ISBN 978-1-4612-1568-4, 1999. doi: 10.1007/978-1-4612-1568-4 18

    work page doi:10.1007/978-1-4612-1568-4 1999

  2. [2]

    3D imaging of nanomaterials by discrete tomography

    Batenburg K, Bals S, Sijbers J, K ¨ubel 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

    work page doi:10.1016/j.ultramic.2009.01.009 2009

  3. [3]

    Three-dimensional atomic imaging of crystalline nanoparticles

    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

    work page doi:10.1038/nature09741 2011

  4. [4]

    Geometric Tomography

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

    work page 1995

  5. [5]

    Discrete Tomography - Foundations, Algorithms and Applications

    Herman GT, Kuba A. Discrete Tomography - Foundations, Algorithms and Applications. Birkhauser,

    work page

  6. [6]

    Advances in Discrete Tomography and Its Applications

    Herman GT, Kuba A. Advances in Discrete Tomography and Its Applications. Birkhauser, 2007. ISBN- 0817636145

    work page 2007

  7. [7]

    A theorem on flows in networks

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

    work page doi:10.2140/pjm 1957

  8. [8]

    Combinatorial properties of matrices of zeros and ones

    Ryser H. Combinatorial properties of matrices of zeros and ones. Can. J. Math., 1957. 9:371–377

    work page 1957

  9. [9]

    The reconstruction of polyominoes from their orthogonal projections

    Woeginger GJ. The reconstruction of polyominoes from their orthogonal projections. Information Pro- cessing 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

    work page doi:10.1016/s0020-0190(00)00162-9 2001

  10. [10]

    Reconstructing Convex Polyominoes from Horizontal and Vertical Projections

    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

    work page doi:10.1016/0304-3975(94)00293-2 1996

  11. [11]

    Determination of finite sets by X-rays

    Gardner R, Gritzmann P. Determination of finite sets by X-rays. Transactions of the American Mathemat- ical Society, 1997. 349(6):2271—-2295

    work page 1997

  12. [13]

    Ambiguity Results in the Characterization of hv-convex Polyominoes from Projections

    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 Interna- tional Conference, DGCI 2017, Vienna, Austria, September 19-21, 2017, Proceedings. 2017 pp. 147–158. doi:10.1007/978-3-319-66272-5 13

    work page doi:10.1007/978-3-319-66272-5 2017

  13. [14]

    First Steps in the Algorithmic Reconstruction of Digital Convex Sets

    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 ´E (eds.), Combinatorics on Words - 11th International Conference, WORDS 2017, Montr ´eal, QC, Canada, September 11-15, 2017, Proceedings, volume 10432 of Lecture Notes in Computer Science...

    work page doi:10.1007/978-3-319-66396-8 2017

  14. [15]

    Properties of SAT Formulas Characterizing Convex Sets with Given Projections

    Marco ND, Frosini A. Properties of SAT Formulas Characterizing Convex Sets with Given Projections. In: Baudrier ´E, Naegel B, Kr¨ahenb¨uhl A, Tajine M (eds.), Discrete Geometry and Mathematical Morphol- ogy - Second International Joint Conference, DGMM 2022, Strasbourg, France, October 24-27, 2022, Proceedings, volume 13493 of Lecture Notes in Computer Sc...

    work page doi:10.1007/978-3-031-19897-7 2022

  15. [16]

    Regular switching components

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

    work page doi:10.1016/j.tcs.2019.01.010 2019

  16. [17]

    Characterization of hv-Convex Sequences

    Dulio P, Frosini A. Characterization of hv-Convex Sequences. J. Math. Imaging Vis., 2022. 64(7):771–

    work page 2022

  17. [18]

    doi:10.1007/s10851-022-01093-z

    work page doi:10.1007/s10851-022-01093-z

  18. [19]

    On Some Geometric Aspects of the Class of hv-Convex Switching Components

    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 Inter- national Joint Conference, DGMM 2021, Uppsala, Sweden, May 24-27, 2021, Proceedings, volume 12708 of Lecture Notes in Computer Science. Springer, 2021 pp. 2...

    work page doi:10.1007/978-3-030-76657-3 2021

  19. [20]

    Further steps on the reconstruction of con- vex polyominoes from orthogonal projections

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

    work page doi:10.1007/s10878-021-00751-z 2022

  20. [21]

    Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses

    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

    work page doi:10.1016/j.tcs.2019.01.001 2019

  21. [22]

    Reconstruction of convex lattice sets from tomographic projections in quartic time

    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

    work page doi:10.1016/j.tcs.2008.06.003 2008

  22. [23]

    Fast Filling Operations Used in the Reconstruction of Convex Lattice Sets

    Brunetti S, Daurat A, Kuba A. Fast Filling Operations Used in the Reconstruction of Convex Lattice Sets. In: Kuba A, Ny ´ul LG, Pal´agyi K (eds.), Discrete Geometry for Computer Imagery. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006 pp. 98–109. doi:10.1007/11907350 9

    work page doi:10.1007/11907350 2006

  23. [24]

    Plass, and Robert Endre Tarjan

    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

    work page doi:10.1016/0020-0190(79)90002-4 1979

  24. [25]

    Dynamic planar convex hull

    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

    work page doi:10.1109/sfcs.2002.1181985 2002