An unknown planar discrete set of points A can be inspected by means of a probe P of generic shape that moves around it, and reveals, for each position, the number of its elements as a magnifying glass. All the data collected during this process can be naturally arranged in an integer matrix that we call the scan of the starting set A w.r.t. the probe P. In [10], Nivat conjectured that a discrete set whose scan w.r.t. an exact probe is k-homogeneous, shows a strong periodical behavior, and it can be decomposed into smaller 1-homogeneous subsets. In this paper, we prove this conjecture to be true when the probe is a diamond, and then we extend this result to exact polyominoes that can regarded as balls in a generalized L-1 norm of Z(2). Then we provide experimental evidence that the conjecture holds for each exact polyomino of small dimension, using the mathematical software Sage [13]. Finally, we give some hints to solve the related reconstruction problem.

Battaglino, D., Frosini, A., Rinaldi, S. (2013). A decomposition theorem for homogeneous sets with respect to diamond probes. COMPUTER VISION AND IMAGE UNDERSTANDING, 117(4), 319-325 [10.1016/j.cviu.2012.09.009].

A decomposition theorem for homogeneous sets with respect to diamond probes

BATTAGLINO, DANIELA;RINALDI, SIMONE
2013-01-01

Abstract

An unknown planar discrete set of points A can be inspected by means of a probe P of generic shape that moves around it, and reveals, for each position, the number of its elements as a magnifying glass. All the data collected during this process can be naturally arranged in an integer matrix that we call the scan of the starting set A w.r.t. the probe P. In [10], Nivat conjectured that a discrete set whose scan w.r.t. an exact probe is k-homogeneous, shows a strong periodical behavior, and it can be decomposed into smaller 1-homogeneous subsets. In this paper, we prove this conjecture to be true when the probe is a diamond, and then we extend this result to exact polyominoes that can regarded as balls in a generalized L-1 norm of Z(2). Then we provide experimental evidence that the conjecture holds for each exact polyomino of small dimension, using the mathematical software Sage [13]. Finally, we give some hints to solve the related reconstruction problem.
Battaglino, D., Frosini, A., Rinaldi, S. (2013). A decomposition theorem for homogeneous sets with respect to diamond probes. COMPUTER VISION AND IMAGE UNDERSTANDING, 117(4), 319-325 [10.1016/j.cviu.2012.09.009].
File in questo prodotto:
File Dimensione Formato  
probes.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 469.42 kB
Formato Adobe PDF
469.42 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/11365/46371
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo