Mathematical and algorithmical analysis of geometric reconstruction tasks arising in refraction- and diffraction-based tomography
Final Report Abstract
During the project we dealt with various different tasks arising within the realm of refractionand diffraction-based tomography. Even though our main emphasis was on the mathematical modeling and analysis, their computational complexity and the development of appropriate algorithms, some subprojects actually involved practical computations on measured experimental data coming from partners from other fields. In fact, we attend challenging issues in plasma physics (particle tracking) and in material science (grain indexing and grain reconstruction). Hence we can structure our work as follows: • Develop appropriate mathematical models of the measurement procedures; • Analyze the mathematics of the inverse problem of reconstruction; • Determine the complexity of the related algorithmic tasks; • Develop practical algorithms; • Apply the gained knowledge to practical problems on real-world experimental data. As it turned out, the subfield of inverse problems as identified in our project proposal is mathematically even richer than we had expected. In fact, mathematically, questions of grain indexing where, in particular, the orientations of the grains within a compound material have to be identified from diffraction measurements involve techniques from the geometry of numbers. Further, characterizing the shape of grains from diffraction measurements of some of their moments turned out to be solvable with the aid of new efficient tools from data analysis (constrained clustering) that had been developed and studied in a different context in our research group before. Once this connection was established, new extension of geometric clustering and diagrams developed, and connections to stochastic geometry emerged. As it turned out, we can characterize grain maps now to a formally unknown precision. Also, our study of the reconstruction of paths of particles in turbulent plasma from tomographic data have lead to very efficient algorithms that have been used in the experimental study of gliding arc discharges. More surprisingly, questions emerging from particle tracking lead to a thorough study of a certain model for multi-modal imaging. In fact, we could derive a polynomial-time algorithm for double resolution where a coarser image is enhanced by tomographic data, but we could also identify various unexpected complexity jumps. Hence the research interplay of discrete mathematics, convex geometry, geometry of numbers, optimization, imaging, algorithmics and computational complexity lead to new theoretical insight and new algorithms, which are in use in other fields. Actually our results on grain mapping sparked new questions in material sciences.
Publications
- “Uniqueness in Discrete Tomography: Three Remarks and a Corollary”. In: SIAM J. Discrete Math. 25.4 (2011), pp. 1589– 1599
P. Gritzmann, B. Langfeld, and M. Wiegelmann
- “Geometric reconstruction methods for electron tomography”. In: Ultramicroscopy 128.C (2013), pp. 42–54
A. Alpers, R. J. Gardner, S. König, R. S. Pennington, C. B. Boothroyd, L. Houben, R. E. Dunin-Borkowski, and K. J. Batenburg
(See online at https://doi.org/10.1016/j.ultramic.2013.01.002) - “Coloring d-embeddable k-uniform hypergraphs”. In: Discrete Comput. Geom. 52.4 (2014), pp. 663–679
C. G. Heise, K. Panagiotou, O. Pikhurko, and A. Taraz
(See online at https://doi.org/10.1007/s00454-014-9641-2) - “3D particle tracking velocimetry using dynamic discrete tomography”. In: Comput. Phys. Commun. 187.1 (2015), pp. 130–136
A. Alpers, P. Gritzmann, D. Moseev, and M. Salewski
(See online at https://doi.org/10.1016/j.cpc.2014.10.022) - “Generalized balanced power diagrams for 3D representations of polycrystals”. In: Phil. Mag. 95.9 (2015), pp. 1016–1028
A. Alpers, A. Brieden, P. Gritzmann, A. Lyckegaard, and H. F. Poulsen
(See online at https://doi.org/10.1080/14786435.2015.1015469) - “Measurements of 3D slip velocities and plasma column lengths of a gliding arc discharge”. In: Appl. Phys. Lett. 106.4 (2015), pp. 044101-1–4
J. Zhu, J. Gao, A. Ehn, M. Aldén, Z. Li, D. Moseev, Y. Kusano, M. Salewski, A. Alpers, P. Gritzmann, and M. Schwenk
(See online at https://doi.org/10.1063/1.4906928) - “The smallest sets of points not determined by their x-rays”. In: Bull. Lond. Math. Soc. 47.1 (2015), pp. 171–176
A. Alpers and D. G. Larman
(See online at https://doi.org/10.1112/blms/bdu111) - On double-resolution imaging and discrete tomography
A. Alpers and P. Gritzmann
- “Discrete tomography of model sets: Reconstruction and uniqueness”. In: Aperiodic Order, Vol. 2: Crystallography and Almost Periodicity. Ed. by M. Baake and U. Grimm. Cambridge University Press, New York, 2017, pp. 39–71
U. Grimm, P. Gritzmann, and C. Huck
- “Reconstructing binary matrices under window constraints from their row and column sums”, in Fund. Inf.
A. Alpers and P. Gritzmann
