Tile-Packing Tomography Is \mathbb{NP}-hardReport as inadecuate




Tile-Packing Tomography Is \mathbb{NP}-hard - Download this document for free, or read online. Document in PDF available to download.

Algorithmica

, Volume 64, Issue 2, pp 267–278

First Online: 19 February 2011Received: 01 July 2010Accepted: 03 February 2011

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 \\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.

KeywordsTilings Discrete tomography \\mathbb{NP}\-hardness Affine independence  Download to read the full article text



Author: Marek Chrobak - Christoph Dürr - Flavio Guíñez - Antoni Lozano - Nguyen Kim Thang

Source: https://link.springer.com/







Related documents