Yan Gerard - Reconstruction of Convex Sets from One or Two X-rays

fi:10329 - Fundamenta Informaticae, September 21, 2023, Volume 189, Issue 2: Tomography and Applications 2022
Reconstruction of Convex Sets from One or Two X-raysArticle

Authors: Yan Gerard

    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.


    Volume: Volume 189, Issue 2: Tomography and Applications 2022
    Published on: September 21, 2023
    Accepted on: July 10, 2023
    Submitted on: November 20, 2022
    Keywords: Computer Science - Computational Geometry,52C45,I.3.5

    Consultation statistics

    This page has been seen 90 times.
    This article's PDF has been downloaded 68 times.