Reconstruction of Convex Sets from One or Two X-rays

• Autorzy: Gerard Yan

Identyfikatory

DOI

10.3233/FI-222155

• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

Discrete Tomography Polyomino Digital Convex sets Filling operations Switching Componen

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 2
• Strony: 113--143
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Gerard Yan

• Universit´e Clermont Auvergne, LIMOS, France

Bibliografia

• [1] Carazo JM, Sorzano CO, Rietzel E, Schrӧder R, Marabini R. Discrete Tomography in Electron Microscopy, pp. 405–416. Birkh¨auser 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 ´E (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 ´E, Naegel B, Krӓhenbühl A, Tajine M (eds.), Discrete Geometry and Mathematical Morphology - Second International Joint Conference, DGMM 2022, 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, Nyul LG, Pal´agyi K (eds.), Discrete Geometry for Computer Imagery. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006 pp. 98–109. doi:10.1007/11907350 9.
• [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