Homepage of the Chair  ->  Applied Geometry & Discrete Mathematics  ->  Research Topics  ->  Discrete Tomography

Applied Geometry & Discrete Mathematics

---

Discrete Tomography

High Resolution Transmission Electron Microscopy enables modern materials like electronic construction elements to be characterized on the atomic scale. This kind of microscopy gives a weighted projection of the three-dimensional object on a two-dimensional plane. A technique based on HRTEM, the QUantitative ANalysis of The Information from Transmission Electron Microscopy, can effectively measure the number of atoms in a crystal lying on each line parallel to certain directions, [8], [7]. However, in this method, the information about the position (height) of the atoms is missing on the lines. This ambiguity can be reduced if the object is tipped over relatively to the electronic beam.

In many problems (e.g., determining inner border surface), it is necessary to reconstruct the complete three-dimensional structure from these weighted projections. So we are interested in the border surface structure of silicon/silicon dioxide to be able to draw conclusions from a quality control on the quality of semiconductor materials, which must have a sufficiently smooth surface for the further treatment in computer chips. For metallic alloys the form and the composition of small crystalline discharges or atom clusters are relevant to be able to set some determined material properties.

Motivated by the improvements in the physical-technical area, the mathematical field of the discrete tomography deals with the analysis of the discrete reconstruction problem and the development of efficient algorithms.

In the "macroscopical field" the mathematics of the inversion problem is well understood; its share was essential in the development of computerized tomography, which was successful for example in medicine in visualizing human organs. The objects, which are observed, are composed by a lot of atoms, such that a number of atoms of the scale 10²³ is lying on each beam; a discrete model is of course not feasible. Only a continuous model can bring success for the computerized tomography of macroscopical objects. But on the atomic scale the problem loses its continuous nature and must be modelled discretely. Since the number of atoms can be determined on the lines, the atoms will be interpreted as points, such that mathematically (ideally) the problem is to reconstruct a set of points in the three-dimensional space from their two-dimensional "discrete X-rays".

On the physical side, only few X-rays can be used, because they distroy the structure quite fast. Moreover, due to the limited resolution ability, QUANTITEM can distinguish the different lines parallel to only certain directions. For technical reasons, these directions lie on a plane.

Since in general a finite number of lattice X-rays is not sufficient for a unique reconstruction of an atomic structure, some restrictions on the set of points are necessary for proving uniqueness statements with only a finite number of lattice X-rays. In [3], with methods of geometry and of algebraic number theory, a problem of L. Shepp is solved; the paper shows that convexe lattice sets are uniquely determined through only four suitable discrete lattice X-rays. This way a stability statement for a result of Gardner & McMullen [6] from the field of continuous "geometric tomography" is also found. Furthermore it is shown that any seven lattice X-rays determine uniquely the finite convexe lattice sets. Besides, interactive technics of successive determination are studied and best possible results are achieved too (see also [2]). Of course the property of convexity is too restrictive for a lot of the relevant uses. Weakenings on "direction convexity" seem physically on the one hand to be reasonable, mathematically on the other hand to allow possible restrictions of the ambiguities. Corresponding studies will be carried out in this research project.

On the algorithmic side the complexity of the relevant problems can be completely determined. In the case of two X-rays the reconstruction problem can be transformed into a Max-Flow problem and so is efficiently solvable. In the case of more than two X-rays the problem becomes NP-complete in the strong sense, [4]. Analogous statements are valid for higher dimensional X-rays and for the polyatomic case, i.e., the case with crystalline structures, which have several kinds of atoms (that problem is actually NP-complete with two X-rays, if there are at least three kinds of different atoms, [5][1]).

In cooperation with P. Schwander, a physicist in the institute for semiconductor physics, Frankfurt/Oder, who plays a decisive role in the development and in the further development of QUANTITEM ([8], [7]), some algorithms, which are based on methods of polyhedral combinatorics on the one hand and on algebraic test set theory on the other hand, are created to be able to determine the complete three-dimensional structure approximatively from the practical physical records. Here possible data insufficiencies are to be considered, such that besides the data errors and the uncomplete information (ambiguity), the algorithms which are used restrict the physical structure and give possible variability width.

  BMBF-project Discrete Tomography

  Graduate program - Workgroup Discrete Optimization

Bibliography

1

M. Chrobak and C. Dürr.
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms.
to appear.

2

R.J. Gardner and P. Gritzmann.
Successive determination and verification of polytopes by their X-rays.
J. Lond. Math. Soc., II. Ser., 50(2):375-391, 1994.

3

R.J. Gardner and P. Gritzmann.
Discrete tomography: determination of finite sets by x-rays.
Trans. Am. Math. Soc., 349(6):2271-2295, 1997.

4

R.J. Gardner, P. Gritzmann, and D. Prangenberg.
On the computational complexity of reconstructing lattice sets from their X-rays.
Discrete Mathematics, to appear.

5

R.J. Gardner, P. Gritzmann, and D. Prangenberg.
On the computational complexity of determining polyatomic structures by X-rays.
Theoretical Computer Science, to appear.

6

R.J. Gardner and P. McMullen.
On Hammer's X-ray problem.
J. Lond. Math. Soc., 21(2):171-175, 1980.

7

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:131-155, 1995.

8

P. Schwander, C. Kisielowski, 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(25):4150-4153, 1993.

Publications of the research group in the field of Discrete Tomography