| Autor: |
Chrobak, Marek, Dürr, Christoph, Guíñez, Flavio, Lozano, Antoni, Thang, Nguyen Kim |
| Zdroj: |
Computing & Combinatorics (9783642140303); 2010, p254-263, 10p |
| Abstrakt: |
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 ]> -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 ]> -hard for all tiles other than bars. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
