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, 65-78.

Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays.

BRUNETTI, SARA;DEL LUNGO, ALBERTO;
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.
2001
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, 65-78.
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/4133
 Attenzione

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