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 Z2, 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.

Dulio, P., Frosini, A., Pagani, S. M. C., Rinaldi, S., Ambiguous reconstructions of hv-convex polyominoes, <<DISCRETE MATHEMATICS>>, 2020; 343 (10): 111998-N/A. [doi:10.1016/j.disc.2020.111998] [http://hdl.handle.net/10807/168338]

Ambiguous reconstructions of hv-convex polyominoes

Pagani, S. M. C.
;
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 Z2, 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.
Inglese
Dulio, P., Frosini, A., Pagani, S. M. C., Rinaldi, S., Ambiguous reconstructions of hv-convex polyominoes, <<DISCRETE MATHEMATICS>>, 2020; 343 (10): 111998-N/A. [doi:10.1016/j.disc.2020.111998] [http://hdl.handle.net/10807/168338]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10807/168338
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact