An algorithm reconstructing convex lattice sets

In this paper, we study the problem of reconstructing special lattice sets from X-rays in a finite set of prescribed directions. We present the class of "Q-convex" sets which is a new class of subsets of Z(2) having a certain kind of weak connectedness. The main result of this paper is a polynomial-time algorithm solving the reconstruction problem for the "Q-convex" sets. These sets are uniquely determined by certain finite sets of directions. As a result, this algorithm can be used for reconstructing convex subsets of Z(2) from their X-rays in some suitable sets of four lattice directions or in any set of seven mutually nonparallel lattice directions. (C) 2003 Elsevier B.V. All rights reserved.