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