Antoni Lozano

  1. Tile Packing Tomography is NP-hard.

    Authors: Marek Chrobak, Christoph Durr, Flavio Guinez, Antoni Lozano, Nguyen Kim Thang
    Subjects: Computational Complexity
    Abstract

    Discrete tomography deals with reconstructing finite spatial objects from
    lower dimensional projections and has applications for example in timetable
    design. In this paper we consider the problem of reconstructing a tile packing
    from its row and column projections. It consists of disjoint copies of a fixed
    tile, all contained in some rectangular grid. The projections tell how many
    cells are covered by a tile in each row and column. How difficult is it to
    construct a tile packing satisfying given projections?

Syndicate content