×

Discrete tomography: Determination of finite sets by X-rays. (English) Zbl 0873.52015

Summary: We study the determination of finite subsets of the integer lattice \(\mathbb{Z}^n\), \(n\geq 2\), by \(X\)-rays. In this context, an \(X\)-ray of a set in a direction \(u\) gives the number of points in the set of each line parallel to \(u\). For practical reasons, only \(X\)-rays in lattice directions, that is, directions parallel to a nonzero vector in the lattice, are permitted. By combining methods from algebraic number theory and convexity, we prove that there are four prescribed lattice directions such that convex subsets of \(\mathbb{Z}^n\) (i.e., finite subsets \(F\) with \(F=\mathbb{Z}^n\cap \text{conv }F\)) are determined, among all such sets, by their \(X\)-rays in these directions. We also show that three \(X\)-rays do not suffice for this purpose. This answers a question of Larry Shepp, and yields a stability result related to Hammer’s \(X\)-ray problem. We further show that any set of seven prescribed mutually nonparallel lattice directions in \(\mathbb{Z}^2\) have the property that convex subsets of \(\mathbb{Z}^2\) are determined, among all such sets, by their \(X\)-rays in these directions. We also consider the use of orthogonal projections in the interactive technique of successive determination, in which the information from previous projections can be used in deciding the direction for the next projection. We obtain results for finite subsets of the integer lattice and also for arbitrary finite subsets of Euclidean space which are the best possible with respect to the number of projections used.

MSC:

52C05 Lattices and convex bodies in \(2\) dimensions (aspects of discrete geometry)
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
68T10 Pattern recognition, speech recognition
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
82D25 Statistical mechanics of crystals
92C55 Biomedical imaging and signal processing
Full Text: DOI

References:

[1] E. Barcucci, A. Del Lungo, M. Nivat, and R. Pinzani, Reconstructing convex polyominoes from their horizontal and vertical projections, Theoretical Comput. Sci. 155 (1996), 321-347. CMP 96:09 · Zbl 0872.68134
[2] F. Beauvais, Reconstructing a set or measure with finite support from its images, Ph. D. dissertation, University of Rochester, Rochester, New York, 1987.
[3] G. Bianchi and M. Longinetti, Reconstructing plane sets from projections, Discrete Comput. Geom. 5 (1990), no. 3, 223 – 242. · Zbl 0703.52002 · doi:10.1007/BF02187787
[4] Shi-kuo Chang, The reconstruction of binary patterns from their projectionw, Comm. ACM 14 (1971), 21 – 25. · Zbl 0214.42603 · doi:10.1145/362452.362471
[5] H. E. Chrestenson, Solution to Problem 5014, Amer. Math. Monthly 70 (1963), 447-448.
[6] M. G. Darboux, Sur un problème de géométrie élémentaire, Bull. Sci. Math. 2 (1878), 298-304. · JFM 10.0360.01
[7] Herbert Edelsbrunner and Steven S. Skiena, Probing convex polygons with X-rays, SIAM J. Comput. 17 (1988), no. 5, 870 – 882. · doi:10.1137/0217054
[8] P. C. Fishburn, J. C. Lagarias, J. A. Reeds, and L. A. Shepp, Sets uniquely determined by projections on axes. II. Discrete case, Discrete Math. 91 (1991), no. 2, 149 – 159. · Zbl 0752.44002 · doi:10.1016/0012-365X(91)90106-C
[9] R. J. Gardner, Geometric Tomography, Cambridge University Press, New York, 1995. CMP 96:02 · Zbl 1042.52501
[10] R. J. Gardner and P. Gritzmann, Successive determination and verification of polytopes by their X-rays, J. London Math. Soc. (2) 50 (1994), 375-391. · Zbl 0813.52012
[11] R. J. Gardner, P. Gritzmann, and D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays, (1996), in preparation. · Zbl 0947.68160
[12] R. J. Gardner and P. McMullen, On Hammer’s X-ray problem, J. London Math. Soc. (2) 21 (1980), no. 1, 171 – 175. · Zbl 0417.52005 · doi:10.1112/jlms/s2-21.1.171
[13] R. Gordon and G. T. Herman, Reconstruction of pictures from their projections, Comm. Assoc. Comput. Machinery 14 (1971), 759-768. · Zbl 0225.68053
[14] Fernando Q. Gouvêa, \?-adic numbers, Universitext, Springer-Verlag, Berlin, 1993. An introduction. · Zbl 0786.11001
[15] A. Heppes, On the determination of probability distributions of more dimensions by their projections, Acta Math. Acad. Sci. Hungar. 7 (1956), 403-410. · Zbl 0072.34402
[16] C. Kisielowski, P. Schwander, F. H. Baumann, M. Seibt, Y. Kim, and A. Ourmazd, An approach to quantitative high-resolution transmission electron microscopy of crystalline materials, Ultramicroscopy 58 (1995), 131-155.
[17] Neal Koblitz, \?-adic numbers, \?-adic analysis, and zeta-functions, 2nd ed., Graduate Texts in Mathematics, vol. 58, Springer-Verlag, New York, 1984. · Zbl 0364.12015
[18] D. Kölzow, A. Kuba, and A. Volčič, An algorithm for reconstructing convex bodies from their projections, Discrete Comput. Geom. 4 (1989), no. 3, 205 – 237. · Zbl 0669.52001 · doi:10.1007/BF02187723
[19] G. G. Lorentz, A problem of plane measure, Amer. J. Math. 71 (1949), 417-426. · Zbl 0032.19701
[20] A. Rényi, On projections of probability distributions, Acta Math. Acad. Sci. Hungar. 3 (1952), 131-142. · Zbl 0048.10804
[21] Herbert John Ryser, Combinatorial mathematics, The Carus Mathematical Monographs, No. 14, Published by The Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. · Zbl 0302.05001
[22] P. Schwander, C. Kisielowski, M. Seibt, F. H. Baumann, Y. Kim, and A. Ourmazd, Mapping projected potential, interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy, Physical Review Letters 71 (1993), 4150-4153.
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.