The core problem of discrete tomography, i.e., the faithful reconstruction of an unknown discrete object from projections along a given set of directions, is ill-posed in general. When further constraints are imposed on the object or on the employed directions, uniqueness of the reconstruction can be obtained. It is the case, for example, of convex lattice sets in Z^2, for which a theorem by Gardner and Gritzmann assures the faithful reconstruction when suitable sets of directions are considered. It was conjectured that a similar result holds for the class of hv-convex polyominoes. In this paper we are concerned with this conjecture, providing new 4-tuples of discrete directions that do not lead to a unique reconstruction of hv-convex polyominoes, underlining the relevant structural difference with the class of convex sets. Our result is based on the recursive definition of new hv-convex switching components on discrete sets along four directions.
Ambiguous reconstructions of hv-convex polyominoes / Dulio, Paolo; Frosini, Andrea; Pagani, Silvia M.C.; Rinaldi, Simone. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - ELETTRONICO. - 343:(2020), pp. 1-12. [10.1016/j.disc.2020.111998]
Ambiguous reconstructions of hv-convex polyominoes
Frosini, Andrea;
2020
Abstract
The core problem of discrete tomography, i.e., the faithful reconstruction of an unknown discrete object from projections along a given set of directions, is ill-posed in general. When further constraints are imposed on the object or on the employed directions, uniqueness of the reconstruction can be obtained. It is the case, for example, of convex lattice sets in Z^2, for which a theorem by Gardner and Gritzmann assures the faithful reconstruction when suitable sets of directions are considered. It was conjectured that a similar result holds for the class of hv-convex polyominoes. In this paper we are concerned with this conjecture, providing new 4-tuples of discrete directions that do not lead to a unique reconstruction of hv-convex polyominoes, underlining the relevant structural difference with the class of convex sets. Our result is based on the recursive definition of new hv-convex switching components on discrete sets along four directions.File | Dimensione | Formato | |
---|---|---|---|
ambiguous rec of hv-convex polyominoes.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
401.19 kB
Formato
Adobe PDF
|
401.19 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.