An introduction to periodical discrete sets from a tomographical perspective
In this paper we introduce a new class of binary matrices whose entries show periodical configurations, and we furnish a first approach to their analysis from a tomographical point of view. In particular we propose a polynomial-time algorithm for reconstructing matrices with a special periodical behavior from their horizontal and vertical projections. We succeeded in our aim by using a reduction involving polyominoes which can be characterized by means of 2 - SAT formulas. (c) 2005 Elsevier B.V. All rights reserved.
polyomino discrete tomography computational complexity 2-sat reduction