In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass of lattice sets (having some connectivity properties) from its X-rays in directions (1,0), (0,1) and (1,1). This algorithm can be easily extended to contexts having more than three X-rays.
Barcucci, E., Brunetti, S., DEL LUNGO, A., Nivat, M. (2001). Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays. DISCRETE MATHEMATICS, 241(1-3), 65-78 [10.1016/S0012-365X(01)00110-8].
Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays
BRUNETTI S.;DEL LUNGO A.;
2001-01-01
Abstract
In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass of lattice sets (having some connectivity properties) from its X-rays in directions (1,0), (0,1) and (1,1). This algorithm can be easily extended to contexts having more than three X-rays.
| File | Dimensione | Formato | |
|---|---|---|---|
|
BBDNDM01.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
399.42 kB
Formato
Adobe PDF
|
399.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/4133
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo