Discrete tomography: Determination of finite sets by Xrays
Authors:
R. J. Gardner and Peter Gritzmann
Journal:
Trans. Amer. Math. Soc. 349 (1997), 22712295
MSC (1991):
Primary 52C05, 52C07; Secondary 52A20, 52B20, 68T10, 68U05, 82D25, 92C55
MathSciNet review:
1376547
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We study the determination of finite subsets of the integer lattice , , by Xrays. In this context, an Xray of a set in a direction gives the number of points in the set on each line parallel to . For practical reasons, only Xrays 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 Xrays in these directions. We also show that three Xrays do not suffice for this purpose. This answers a question of Larry Shepp, and yields a stability result related to Hammer's Xray 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 Xrays 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), 321347. 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
(91f:68200), http://dx.doi.org/10.1007/BF02187787
 4.
Shikuo
Chang, The reconstruction of binary patterns from their
projectionw, Comm. ACM 14 (1971), 21–25. MR 0285156
(44 #2379)
 5.
H. E. Chrestenson, Solution to Problem 5014, Amer. Math. Monthly 70 (1963), 447448.
 6.
M. G. Darboux, Sur un problème de géométrie élémentaire, Bull. Sci. Math. 2 (1878), 298304.
 7.
Herbert
Edelsbrunner and Steven
S. Skiena, Probing convex polygons with Xrays, SIAM J.
Comput. 17 (1988), no. 5, 870–882. MR 961045
(89i:52002), http://dx.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
(92m:28009), http://dx.doi.org/10.1016/0012365X(91)90106C
 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 Xrays, J. London Math. Soc. (2) 50 (1994), 375391.
 11.
R. J. Gardner, P. Gritzmann, and D. Prangenberg, On the computational complexity of reconstructing lattice sets from their Xrays, (1996), in preparation.
 12.
R.
J. Gardner and P.
McMullen, On Hammer’s Xray problem, J. London Math.
Soc. (2) 21 (1980), no. 1, 171–175. MR 576194
(81m:52009), http://dx.doi.org/10.1112/jlms/s221.1.171
 13.
R. Gordon and G. T. Herman, Reconstruction of pictures from their projections, Comm. Assoc. Comput. Machinery 14 (1971), 759768.
 14.
Fernando
Q. Gouvêa, 𝑝adic numbers, Universitext,
SpringerVerlag, Berlin, 1993. An introduction. MR 1251959
(95b:11111)
 15.
A.
Heppes, On the determination of probability distributions of more
dimensions by their projections, Acta Math. Acad. Sci. Hungar.
7 (1956), 403–410 (English, with Russian summary).
MR
0085646 (19,70f)
 16.
C. Kisielowski, P. Schwander, F. H. Baumann, M. Seibt, Y. Kim, and A. Ourmazd, An approach to quantitative highresolution transmission electron microscopy of crystalline materials, Ultramicroscopy 58 (1995), 131155.
 17.
Neal
Koblitz, 𝑝adic numbers, 𝑝adic analysis, and
zetafunctions, 2nd ed., Graduate Texts in Mathematics, vol. 58,
SpringerVerlag, New York, 1984. MR 754003
(86c:11086)
 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
(90d:52002), http://dx.doi.org/10.1007/BF02187723
 19.
G.
G. Lorentz, A problem of plane measure, Amer. J. Math.
71 (1949), 417–426. MR 0028925
(10,519c)
 20.
A.
Rényi, On projections of probability distributions,
Acta Math. Sci. Hungar. 3 (1952), 131–142 (English,
with Russian summary). MR 0053422
(14,771e)
 21.
Herbert
John Ryser, Combinatorial mathematics, The Carus Mathematical
Monographs, No. 14, Published by The Mathematical Association of America,
1963. MR
0150048 (27 #51)
 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), 41504153.
 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), 321347. 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 Comp. Geom. 5 (1990), 223242. MR 91f:68200
 4.
 S.K. Chang, The reconstruction of binary patterns from their projections, Comm. Assoc. Comput. Machinery 14 (1971), 2124. MR 44:2379
 5.
 H. E. Chrestenson, Solution to Problem 5014, Amer. Math. Monthly 70 (1963), 447448.
 6.
 M. G. Darboux, Sur un problème de géométrie élémentaire, Bull. Sci. Math. 2 (1878), 298304.
 7.
 H. Edelsbrunner and S. S. Skiena, Probing convex polygons with Xrays, SIAM. J. Comp. 17 (1988), 870882. MR 89i:52002
 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), 149159. MR 92m:28009
 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 Xrays, J. London Math. Soc. (2) 50 (1994), 375391.
 11.
 R. J. Gardner, P. Gritzmann, and D. Prangenberg, On the computational complexity of reconstructing lattice sets from their Xrays, (1996), in preparation.
 12.
 R. J. Gardner and P. McMullen, On Hammer's Xray problem, J. London Math. Soc. (2) 21 (1980), 171175. MR 81m:52009
 13.
 R. Gordon and G. T. Herman, Reconstruction of pictures from their projections, Comm. Assoc. Comput. Machinery 14 (1971), 759768.
 14.
 F. Q. Gouvêa, adic Numbers, Springer, New York, 1993. MR 95b:11111
 15.
 A. Heppes, On the determination of probability distributions of more dimensions by their projections, Acta Math. Acad. Sci. Hungar. 7 (1956), 403410. MR 19:70f
 16.
 C. Kisielowski, P. Schwander, F. H. Baumann, M. Seibt, Y. Kim, and A. Ourmazd, An approach to quantitative highresolution transmission electron microscopy of crystalline materials, Ultramicroscopy 58 (1995), 131155.
 17.
 N. Koblitz, adic Numbers, adic Analysis, and ZetaFunctions, 2nd ed., Springer, New York, 1984. MR 86c:11086
 18.
 D. Kölzow, A. Kuba, and A. Vol\v{c}i\v{c}, An algorithm for reconstructing convex bodies from their projections, Discrete Comp. Geom. 4 (1989), 205237. MR 90d:52002
 19.
 G. G. Lorentz, A problem of plane measure, Amer. J. Math. 71 (1949), 417426. MR 10:519c
 20.
 A. Rényi, On projections of probability distributions, Acta Math. Acad. Sci. Hungar. 3 (1952), 131142. MR 14:771e
 21.
 H. J. Ryser, Combinatorial Mathematics, Mathematical Association of America and Quinn & Boden, Rahway, New Jersey, 1963. MR 27:51
 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), 41504153.
Similar Articles
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 982259063
Email:
gardner@baker.math.wwu.edu
Peter Gritzmann
Affiliation:
Fb IV, Mathematik, Universität Trier, D54286 Trier, Germany
Email:
gritzman@dm1.unitrier.de
DOI:
http://dx.doi.org/10.1090/S0002994797017418
PII:
S 00029947(97)017418
Keywords:
Tomography,
discrete tomography,
Xray,
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 DMS9501289; second author supported in part by the Deutsche Forschungsgemeinschaft and by a Max Planck Research Award.
Article copyright:
© Copyright 1997 American Mathematical Society
