In this paper, we study the problem of reconstructing special lattice sets from X-rays in a finite set of prescribed directions. We present the class of "Q-convex" sets which is a new class of subsets of ℤ2 having a certain kind of weak connectedness. The main result of this paper is a polynomial-time algorithm solving the reconstruction problem for the "Q-convex" sets. These sets are uniquely determined by certain finite sets of directions. As a result, this algorithm can be used for reconstructing convex subsets of ℤ2 from their X-rays in some suitable sets of four lattice directions or in any set of seven mutually nonparallel lattice directions.

Brunetti, S., & Daurat, A. (2003). An algorithm reconstructing convex lattice sets. THEORETICAL COMPUTER SCIENCE, 304, 35-57.

An algorithm reconstructing convex lattice sets

BRUNETTI, SARA;
2003

Abstract

In this paper, we study the problem of reconstructing special lattice sets from X-rays in a finite set of prescribed directions. We present the class of "Q-convex" sets which is a new class of subsets of ℤ2 having a certain kind of weak connectedness. The main result of this paper is a polynomial-time algorithm solving the reconstruction problem for the "Q-convex" sets. These sets are uniquely determined by certain finite sets of directions. As a result, this algorithm can be used for reconstructing convex subsets of ℤ2 from their X-rays in some suitable sets of four lattice directions or in any set of seven mutually nonparallel lattice directions.
File in questo prodotto:
File Dimensione Formato  
TCS03.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 372.16 kB
Formato Adobe PDF
372.16 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: http://hdl.handle.net/11365/12356
 Attenzione

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