Tiling Under Tomographic Constraints: A Note on Reconstruction

Title: Tiling Under Tomographic Constraints: A Note on Reconstruction

Research Question: Can we reconstruct a tiling from its projections, given a set of tiles with different shapes?

Methodology: The researchers used a combination of combinatorial analysis and computer simulations to study the problem of reconstructing a tiling from its projections. They considered tiles that are hole-less polyominoes and investigated the complexity of reconstructing a tiling for different sets of tiles.

Results: The researchers proved that for some sets of tiles, the problem of reconstructing a tiling from its projections is NP-complete, meaning that it is computationally difficult and may require exponential time to solve. They also provided a method to determine whether a given set of projections can be realized by a tiling.

Implications: The results of this study have implications for the field of discrete tomography, which involves reconstructing discrete objects from their projections. The study provides insights into the complexity of this problem and may lead to more efficient algorithms for reconstructing tilings from their projections. Additionally, the results may have applications in other areas of combinatorial mathematics and computer science.

Conclusion: In this study, the researchers made progress towards a comprehensive classification of tiling reconstruction problems by proving NP-completeness results for several sets of tiles. They also provided a method to determine whether a given set of projections can be realized by a tiling.

Link to Article: https://arxiv.org/abs/0108010v2 Authors: arXiv ID: 0108010v2