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 D.;Rinaldi S.
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.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.
https://hdl.handle.net/11365/46371
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo