Tile-Packing Tomography Is $\mathbb{NP}$ -hard
Marek Chrobák, Christoph Dürr, Flavio Guíñez, Antoni Lozano, Nguyễn Kim Thắng · Algorithmica · 2011
Discrete tomography deals with reconstructing finite spatial objects from their projections. The objects we study in this paper are called tilings or tile-packings, and they consist of a number of disjoint copies of a fixed tile, where a tile is defined as a connected set of grid points. A row projection specifies how many grid points are covered by tiles in a given row; column projections are defined analogously. For a fixed tile, is it possible to reconstruct its tilings from their projections in polynomial time? It is known that the answer to this question is affirmative if the tile is a bar (its width or height is 1), while for some other types of tiles $\mathbb {NP}$ -hardness results have been shown in the literature. In this paper we present a complete solution to this question by showing that the problem remains $\mathbb {NP}$ -hard for all tiles other than bars.