Filling operations are procedures which are used in Discrete Tomography for the reconstruction of convex lattice sets. In \cite{g98}, an algorithm which performs four of these filling operations has a time complexity of $O(N^2\log(N))$ where $N$ is the size of X-rays. In this paper we improve this algorithm by including a fifth filling operation that is needed for the reconstruction with the same time-complexity. As a consequence the reconstruction of Q-convex sets and convex lattice sets (intersection of a convex polygon with $\ZZ^2$) can be done in $O(N^4\log(N))$-time.

Brunetti, S., Daurat, A., & Kuba, A. (2006). Fast filling operations used in the reconstruction of convex lattice sets. In Discrete Geometry for Computer Imagery (pp.98-102).

Fast filling operations used in the reconstruction of convex lattice sets

BRUNETTI, SARA;
2006

Abstract

Filling operations are procedures which are used in Discrete Tomography for the reconstruction of convex lattice sets. In \cite{g98}, an algorithm which performs four of these filling operations has a time complexity of $O(N^2\log(N))$ where $N$ is the size of X-rays. In this paper we improve this algorithm by including a fifth filling operation that is needed for the reconstruction with the same time-complexity. As a consequence the reconstruction of Q-convex sets and convex lattice sets (intersection of a convex polygon with $\ZZ^2$) can be done in $O(N^4\log(N))$-time.
File in questo prodotto:
File Dimensione Formato  
BDKDGCI06.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 256.34 kB
Formato Adobe PDF
256.34 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/25350
 Attenzione

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