On J-additivity and Bounded Additivity

• Autorzy: Brunetti S. , Peri C.

Identyfikatory

DOI

10.3233/FI-2016-1380

• Języki publikacji: EN

Abstrakty

EN

In this paper we consider the uniqueness issues in Discrete Tomography. A special class of geometric objects, widely considered in the literature, is represented by additive sets. These sets are uniquely determined by their X-rays, and they are also reconstructible in polynomial time by use of linear programming. Recently, additivity has been extended to J-additivity to provide a more general treatment of known concepts and results. A further generalization of additivity, called bounded additivity is obtained by restricting to sets contained in a given orthogonal box. In this work, we investigate these two generalizations from a geometrical point of view and analyze the interplay between them.

Słowa kluczowe

EN

additive set; uniqueness problem; weakly bad configuration; X-ray

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 2
• Strony: 185--195
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Brunetti S.

• Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Via Roma, 56, 53100 Siena - Italy

autor

Peri C.

• Università Cattolica S. C., Via Emilia Parmense, 84, 29122 Piacenza - Italy

Bibliografia

• [1] Gardner RJ, Gritzmann P, Prangenberg D. On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Mathematics. 1999;202(1-3):45–71. Available from: http://dx.doi.org/10.1016/S0012-365X(98)00347-1. doi:10.1016/S0012-365X(98)00347-1.
• [2] Fishburn PC, Shepp LA. Sets of uniqueness and additivity in integer lattices. In: Herman GT, Kuba A, editors. Discrete Tomography. Foundations, Algorithms, and Applications. Appl. Numer. Harmon. Anal. Birkhäuser; 1999. p. 35–58. doi:10.1007/978-1-4612-1568-4_2.
• [3] Fishburn PC, Schwander P, Shepp L, Vanderbei R. The Discrete Radon Transform and Its Approximate Inversion Via Linear Programming. Discrete Applied Mathematics. 1997;75(1):39–61. Available from: http://dx.doi.org/10.1016/S0166-218X(96)00083-2. doi:10.1016/S0166-218X(96)00083-2.
• [4] Gritzmann P, Langfeld B, Wiegelmann M. Uniqueness in Discrete Tomography: Three Remarks and a Corollary. SIAM J Discrete Math. 2011;25(4):1589–1599. Available from: http://dx.doi.org/10.1137/100803262. doi:10.1137/100803262.
• [5] Hajdu L, Tijdeman R. Algebraic aspects of discrete tomography. J reine angew Math. 2001;534:119–128. doi:10.1515/crll.2001.037.
• [6] Hajdu L, Tijdeman R. Algebraic Discrete Tomography. In: Herman GT, Kuba A, editors. Advances in Discrete Tomography and Its Applications. Appl. Numer. Harmon. Anal. Birkhäuser, Boston, MA; 2007. p. 55–81. doi:10.1007/978-0-8176-4543-4_4.
• [7] Brunetti S, Dulio P, Peri C. Discrete Tomography determination of bounded lattice sets from four X-rays. Discrete Applied Mathematics. 2013;161(15):2281–2292. doi:10.1016/j.dam.2012.09.010.
• [8] Brunetti S, Dulio P, Peri C. Discrete Tomography determination of bounded sets in Zn. Discrete Applied Mathematics. 2015;183:20–30. doi:10.1016/j.dam.2014.01.016.
• [9] Brunetti S, Dulio P, Peri C. On bounded additivity in discrete tomography. Theoret Comput Sci. 2016;624:89–100. doi:10.1016/j.tcs.2015.11.022.
• [10] Aharoni R, Herman GT, Kuba A. Binary vectors partially determined by linear equation systems. Discrete Mathematics. 1997;171:1–16. doi:10.1016/S0012-365X(96)00068-4.
• [11] Gritzmann P, Prangenberg D, de Vries S, Wiegelmann M. Success and failure of certain reconstruction and uniqueness algorithms in discrete tomography. International Journal of Imaging Systems and Technology. 1998;9(2-3):101–109.
• [12] Weber S, Schnoerr C, Hornegger J. A linear programming relaxation for binary tomography with smoothness priors. In: 9th International Workshop on Combinatorial Image Analysis. vol. 12 of Electron. Notes Discrete Math. Elsevier, Amsterdam; 2003. p. 243–254.
• [13] Weber S, Schule S, Hornegger J, Schnoerr C. Binary Tomography by Iterating Linear Programs from Noisy Projections. In: Klette R, Žunić J, editors. Combinatorial Image Analysis: 10th International Workshop, IWCIA 2004, Auckland, New Zealand, December 1-3, 2004. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg; 2005. p. 38–51. doi:10.1007/978-3-540-30503-3_3.
• [14] Brunetti S, Dulio P, Peri C. Explicit determination of bounded non-additive sets of uniqueness for four X-rays. In: International Symposium on Image and Signal Processing and Analysis. ISPA; 2013. p. 588–593. doi:10.1109/ISPA.2013.6703808.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).