|
Title:
|
Tile-packing tomography is NP-hard
|
|
Author:
|
Chrobak, Marek; Dürr, Christoph; Guíñez, Flavio; Lozano Bojados, Antoni; Kim Thang, Nguyen
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. LOGPROG - Lògica i Programació |
|
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 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 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 bars. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
-Computational complexity
-Tomography
-Complexitat computacional
-Tomografia |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Conference Object |
|
Share:
|
|
