An Algorithm for Reconstructing Special Lattice Sets from Their Approximate X-rays

We study the problem of reconstructing finite subsets of the integer lattice Z2 from their approximate X-rays in a finite number of prescribed lattice directions. We provide a polynomial-time algorithm for reconstructing Q-convex sets from their “approximate” X-rays. A Qconvex set is a special subset of Z2 having some convexity properties. This algorithm can be used for reconstructing convex subsets of Z2 from their exact X-rays in some sets of four prescribed lattice directions, or in any set of seven prescribed mutually nonparallel lattice directions.