Abstract

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 ?xed tile, where a tile is de?ned 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 ?xed 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 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 NP-hard for all tiles other than bar.