×

On bounded additivity in discrete tomography. (English) Zbl 1338.68257

Summary: In this paper we investigate bounded additivity in Discrete Tomography. This notion has been previously introduced in [the authors, Lect. Notes Comput. Sci. 7749, 288–299 (2013; Zbl 1339.68256)], as a generalization of the original one in [P. C. Fishburn et al., SIAM J. Appl. Math. 50, No. 1, 288–306 (1990; Zbl 0695.44003)], which was given in terms of ridge functions. We exploit results from [the authors, “Explicit determination of bounded non-additive sets of uniqueness for four X-rays”, in: Proceedings of the 8th international IEEE symposium on image and signal processing and analysis, ISPA’13. Los Alamitos, CA: IEEE Computer Society. 588–593 (2013; doi:10.1109/ISPA.2013.6703808); Discrete Appl. Math. 183, 20–30 (2015; Zbl 1319.68233); Lect. Notes Comput. Sci. 8668, 226–237 (2014; Zbl 1339.68257)] to deal with bounded \(S\) non-additive sets of uniqueness, where \(S \subset \mathbb{Z}^n\) contains \(d\) coordinate directions \(\{e_1, \ldots, e_d \}\), \(| S | = d + 1\), and \(n \geq d \geq 3\). We prove that, when the union of two special subsets of \(\{e_1, \ldots, e_d \}\) has cardinality \(k = n\), then bounded \(S\) non-additive sets of uniqueness are confined in a grid \(\mathcal{A}\) having a suitable fixed size in each coordinate direction \(e_i\), whereas, if \(k < n\), the grid \(\mathcal{A}\) can be arbitrarily large in each coordinate direction \(e_i\), where \(i > k\). The subclass of pure bounded \(S\) non-additive sets plays a special role. We also compute explicitly the proportion of bounded \(S\) non-additive sets of uniqueness w.r.t. those additive, as well as w.r.t. the \(S\)-unique sets. This confirms a conjecture proposed by P. C. Fishburn and L. A. Shepp [in: Discrete tomography. Foundations, algorithms, and applications. Basel: Birkhäuser. 35–58 (1999; Zbl 1105.92332)] for the class of bounded sets.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI

References:

[1] Aharoni, R.; Herman, G. T.; Kuba, A., Binary vectors partially determined by linear equation systems, Discrete Math., 171, 1-16 (1997) · Zbl 0877.15004
[2] Brunetti, S.; Del Lungo, A.; Gritzmann, P.; de Vries, S., On the reconstruction of binary and permutation matrices under (binary) tomographic constraints, Theoret. Comput. Sci., 406, 63-71 (2008) · Zbl 1160.68038
[3] Brunetti, S.; Dulio, P.; Peri, C., Characterization of \(\{- 1, 0, 1 \}\) valued functions in discrete tomography under sets of four directions, (Discrete Geometry for Computer Imagery. Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, vol. 6607 (2011)), 394-405 · Zbl 1272.92032
[4] Brunetti, S.; Dulio, P.; Peri, C., Discrete tomography determination of bounded lattice sets from four X-rays, Discrete Appl. Math., 161, 15, 2281-2292 (2013) · Zbl 1278.05051
[5] Brunetti, S.; Dulio, P.; Peri, C., On the non-additive sets of uniqueness in a finite grid, (17th International Conference on Discrete Geometry for Computer Imagery. 17th International Conference on Discrete Geometry for Computer Imagery, DGCI, Sevilla, 2013. 17th International Conference on Discrete Geometry for Computer Imagery. 17th International Conference on Discrete Geometry for Computer Imagery, DGCI, Sevilla, 2013, LNCS, vol. 7749 (2013)), 288-299 · Zbl 1339.68256
[6] Brunetti, S.; Dulio, P.; Peri, C., Explicit determination of bounded non-additive sets of uniqueness for four X-rays, (International Symposium on Image and Signal Processing and Analysis. International Symposium on Image and Signal Processing and Analysis, ISPA (2013)), 588-593 · Zbl 1278.05051
[7] Brunetti, S.; Dulio, P.; Peri, C., Discrete Tomography determination of bounded sets in \(Z^n\), Discrete Appl. Math., 183, 20-30 (2015) · Zbl 1319.68233
[8] Brunetti, S.; Dulio, P.; Peri, C., Non-additive bounded sets of uniqueness in \(Z^n\), (Barcucci, E.; etal., DGCI 2014. DGCI 2014, Lecture Notes in Computer Science, vol. 8668 (2014), Springer-Verlag), 226-237 · Zbl 1339.68257
[9] Brunetti, S.; Dulio, P.; Hajdu, L.; Peri, C., Ghosts in discrete tomography, J. Math. Imaging Vision, 53, 2, 210-224 (2015) · Zbl 1343.68267
[10] Batenburg, K. J.; Fortes, W.; Hajdu, L.; Tijdeman, R., Bounds on the quality of reconstructed images in binary tomography, Discrete Appl. Math., 161, 15, 2236-2251 (2013) · Zbl 1278.05049
[11] Fishburn, P. C.; Lagarias, J. C.; Reeds, J. A.; Shepp, L. A., Sets uniquely determined by projections on axes I. Continuous case, SIAM J. Appl. Math., 50, 1, 288-306 (1990) · Zbl 0695.44003
[12] Fishburn, P. C.; Lagarias, J. C.; Reeds, J. A.; Shepp, L. A., Sets uniquely determined by projections on axes II. Discrete case, Discrete Math., 91, 149-159 (1991) · Zbl 0752.44002
[13] Fishburn, P. C.; Schwander, P.; Shepp, L.; Vanderbei, R., The discrete Radon transform and its approximate inversion via linear programming, Discrete Appl. Math., 75, 39-61 (1997) · Zbl 0879.68103
[14] Fishburn, P. C.; Shepp, L. A., Sets of uniqueness and additivity in integer lattices, (Herman, G. T.; Kuba, A., Discrete Tomography: Foundations, Algorithms and Application (1999), Birkhäuser: Birkhäuser Boston), 35-58 · Zbl 1105.92332
[15] Gritzmann, P.; Langfeld, B.; Wiegelmann, M., Uniquness in discrete tomography: three remarks and a corollary, SIAM J. Discrete Math., 25, 1589-1599 (2011) · Zbl 1237.68239
[16] Hajdu, L., Unique reconstruction of bounded sets in discrete tomography, Electron. Notes Discrete Math., 20, 15-25 (2005) · Zbl 1179.94010
[17] Hajdu, L.; Tijdeman, R., Algebraic aspects of discrete tomography, J. Reine Angew. Math., 534, 119-128 (2001) · Zbl 1058.92029
[18] Hajdu, L.; Tijdeman, R., Algebraic discrete tomography, (Herman, G. T.; Kuba, A., Advances in Discrete Tomography and Its Applications (2007), Birkhäuser: Birkhäuser Boston), 55-81 · Zbl 1130.65127
[19] Kak, A. C.; Slaney, M., Principles of Computerized Tomographic Imaging (2001), SIAM · Zbl 0984.92017
[20] Zhua, J.; Lia, X.; Yeb, Y.; Wang, G., Analysis on the strip-based projection model for discrete tomography, Discrete Appl. Math., 156, 12, 2359-2367 (2008) · Zbl 1144.92027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.