zbMATH — the first resource for mathematics

Reconstruction of lattice sets from their horizontal, vertical and diagonal \(X\)-rays. (English) Zbl 1001.68177
Summary: We study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass of lattice sets (having some connectivity properties) from its X-rays in directions \((1,0)\), \((0,1)\) and \((1, 1)\). This algorithm can be easily extended to contexts having more than three X-rays.

68U10 Computing methodologies for image processing
05B50 Polyominoes
Full Text: DOI