In 1997 R. Gardner and P. Gritzmann proved a milestone result for uniqueness in Discrete Tomography: a finite convex discrete set can be uniquely determined by projections taken in any set of seven planar directions. The number of required directions can be reduced to 4, providing their cross-ratio, arranged in order of increasing angle with the positive x-axis, does not belong to the set {4/3,3/2,2,3,4}. Later studies, supported by experimental evidence, allow us to conjecture that a similar result may also hold for the wider class of hv-convex polyominoes. In this paper we shed some light on the differences between these two classes, providing new 4-tuples of discrete directions that do not lead to a unique reconstruction of hv-convex polyominoes. We reach our main result by a constructive process. This generates switching components along four directions by a recursive composition of only three of them, and then by shifting the obtained structure along the fourth one. Furthermore, we stress the role that the horizontal and the vertical directions have in preserving the hv-convexity property. This is pointed out by showing that these often appear in the 4-tuples of directions that allow uniqueness. A final characterization theorem for hv-convex polyominoes is still left as open question.

Ambiguity results in the characterization of hv-convex polyominoes from projection / Elena, Barcucci; Paolo, Dulio; Andrea, Frosini; Simone, Rinaldi. - STAMPA. - (2017), pp. 147-158. (Intervento presentato al convegno International Conference on Discrete Geometry for Computer Imagery) [10.1007/978-3-319-66272-5_13].

Ambiguity results in the characterization of hv-convex polyominoes from projection

Elena Barcucci;Andrea Frosini
;
2017

Abstract

In 1997 R. Gardner and P. Gritzmann proved a milestone result for uniqueness in Discrete Tomography: a finite convex discrete set can be uniquely determined by projections taken in any set of seven planar directions. The number of required directions can be reduced to 4, providing their cross-ratio, arranged in order of increasing angle with the positive x-axis, does not belong to the set {4/3,3/2,2,3,4}. Later studies, supported by experimental evidence, allow us to conjecture that a similar result may also hold for the wider class of hv-convex polyominoes. In this paper we shed some light on the differences between these two classes, providing new 4-tuples of discrete directions that do not lead to a unique reconstruction of hv-convex polyominoes. We reach our main result by a constructive process. This generates switching components along four directions by a recursive composition of only three of them, and then by shifting the obtained structure along the fourth one. Furthermore, we stress the role that the horizontal and the vertical directions have in preserving the hv-convexity property. This is pointed out by showing that these often appear in the 4-tuples of directions that allow uniqueness. A final characterization theorem for hv-convex polyominoes is still left as open question.
2017
Discrete Geometry for Computer Imagery. DGCI 2017
International Conference on Discrete Geometry for Computer Imagery
Elena, Barcucci; Paolo, Dulio; Andrea, Frosini; Simone, Rinaldi
File in questo prodotto:
File Dimensione Formato  
HV-congettura4.pdf

accesso aperto

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 118.29 kB
Formato Adobe PDF
118.29 kB Adobe PDF
Ambiguity results in the characterization of hv-convex polyominoes.pdf

Accesso chiuso

Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 2.84 MB
Formato Adobe PDF
2.84 MB 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/1104781
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact