The problem of reconstructing a discrete set from its X-rays in a finite number of prescribed directions is NP-complete when the number of prescribed directions is greater than two. In this paper, we consider an interesting subclass of discrete sets having some connectivity and convexity properties and we provide a polynomial-time algorithm for reconstructing a discrete set of this class 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. (2000). Reconstruction of Discrete Sets from Three or More X-Rays. In Algorithms and Complexity (pp.199-210). Berlin : Springer [10.1007/3-540-46521-9_17].
Reconstruction of Discrete Sets from Three or More X-Rays
BRUNETTI, SARA;
2000-01-01
Abstract
The problem of reconstructing a discrete set from its X-rays in a finite number of prescribed directions is NP-complete when the number of prescribed directions is greater than two. In this paper, we consider an interesting subclass of discrete sets having some connectivity and convexity properties and we provide a polynomial-time algorithm for reconstructing a discrete set of this class 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 | |
|---|---|---|---|
|
BBDNCIAC2000.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
5.6 MB
Formato
Adobe PDF
|
5.6 MB | 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/27154