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.
2020
343
1
12
Dulio, Paolo; Frosini, Andrea; Pagani, Silvia M.C.; Rinaldi, Simone
File in questo prodotto:
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.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1195510
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact