Discrete tomography:

Determination of finite sets by X-rays

Authors:
R. J. Gardner and Peter Gritzmann

Journal:
Trans. Amer. Math. Soc. **349** (1997), 2271-2295

MSC (1991):
Primary 52C05, 52C07; Secondary 52A20, 52B20, 68T10, 68U05, 82D25, 92C55

DOI:
https://doi.org/10.1090/S0002-9947-97-01741-8

MathSciNet review:
1376547

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the determination of finite subsets of the integer lattice , , by X-rays. In this context, an X-ray of a set in a direction gives the number of points in the set on each line parallel to . 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 (i.e., finite subsets with ) 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 have the property that convex subsets of 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 numbers of projections used.

**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****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. MR**1036872**, https://doi.org/10.1007/BF02187787**4.**Shi-kuo Chang,*The reconstruction of binary patterns from their projectionw*, Comm. ACM**14**(1971), 21–25. MR**0285156**, https://doi.org/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.**7.**Herbert Edelsbrunner and Steven S. Skiena,*Probing convex polygons with X-rays*, SIAM J. Comput.**17**(1988), no. 5, 870–882. MR**961045**, https://doi.org/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. MR**1124762**, https://doi.org/10.1016/0012-365X(91)90106-C**9.**R. J. Gardner,*Geometric Tomography*, Cambridge University Press, New York, 1995. CMP**96:02****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.**11.**R. J. Gardner, P. Gritzmann, and D. Prangenberg,*On the computational complexity of reconstructing lattice sets from their X-rays*, (1996), in preparation.**12.**R. J. Gardner and P. McMullen,*On Hammer’s X-ray problem*, J. London Math. Soc. (2)**21**(1980), no. 1, 171–175. MR**576194**, https://doi.org/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.**14.**Fernando Q. Gouvêa,*𝑝-adic numbers*, Universitext, Springer-Verlag, Berlin, 1993. An introduction. MR**1251959****15.**A. Heppes,*On the determination of probability distributions of more dimensions by their projections*, Acta Math. Acad. Sci. Hungar.**7**(1956), 403-410. MR**19:70f****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. MR**754003****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. MR**988743**, https://doi.org/10.1007/BF02187723**19.**G. G. Lorentz,*A problem of plane measure*, Amer. J. Math.**71**(1949), 417-426. MR**10:519c****20.**A. Rényi,*On projections of probability distributions*, Acta Math. Acad. Sci. Hungar.**3**(1952), 131-142. MR**14:771e****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. MR**0150048****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.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (1991):
52C05,
52C07,
52A20,
52B20,
68T10,
68U05,
82D25,
92C55

Retrieve articles in all journals with MSC (1991): 52C05, 52C07, 52A20, 52B20, 68T10, 68U05, 82D25, 92C55

Additional Information

**R. J. Gardner**

Affiliation:
Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063

Email:
gardner@baker.math.wwu.edu

**Peter Gritzmann**

Affiliation:
Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany

Email:
gritzman@dm1.uni-trier.de

DOI:
https://doi.org/10.1090/S0002-9947-97-01741-8

Keywords:
Tomography,
discrete tomography,
X-ray,
projection,
lattice,
lattice polygon,
convex body,
$p$-adic valuation

Received by editor(s):
October 3, 1995

Additional Notes:
First author supported in part by the Alexander von Humboldt Foundation and by National Science Foundation Grant DMS-9501289; second author supported in part by the Deutsche Forschungsgemeinschaft and by a Max Planck Research Award.

Article copyright:
© Copyright 1997
American Mathematical Society