Filling operations are procedures which are used in Discrete Tomography for the reconstruction of lattice sets having some convexity constraints. Many algorithms have been published giving fast implementations of these operations, and the best running time [S. Brunetti, A. Daurat, A. Kuba, Fast filling operations used in the reconstruction of convex lattice sets, in: Proc. of DGCI 2006, in: Lecture Notes in Comp. Sci., vol. 4245, 2006, pp. 98–109] is O(N2logN) time, where N is the size of projections. In this paper we improve this result by providing an implementation of the filling operations in O(N2). As a consequence, we reduce the time-complexity of the reconstruction algorithms for many classes of lattice sets having some convexity properties. In particular, the reconstruction of convex lattice sets satisfying the conditions of Gardner–Gritzmann [R.J. Gardner, P. Gritzmann, Discrete tomography: Determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997) 2271–2295] can be performed in O(N4)-time.

Brunetti, S., & Daurat, A. (2008). Reconstruction of convex lattice sets from tomographic projections in quartic time. THEORETICAL COMPUTER SCIENCE, 406, 55-62.

Reconstruction of convex lattice sets from tomographic projections in quartic time

BRUNETTI, SARA;
2008

Abstract

Filling operations are procedures which are used in Discrete Tomography for the reconstruction of lattice sets having some convexity constraints. Many algorithms have been published giving fast implementations of these operations, and the best running time [S. Brunetti, A. Daurat, A. Kuba, Fast filling operations used in the reconstruction of convex lattice sets, in: Proc. of DGCI 2006, in: Lecture Notes in Comp. Sci., vol. 4245, 2006, pp. 98–109] is O(N2logN) time, where N is the size of projections. In this paper we improve this result by providing an implementation of the filling operations in O(N2). As a consequence, we reduce the time-complexity of the reconstruction algorithms for many classes of lattice sets having some convexity properties. In particular, the reconstruction of convex lattice sets satisfying the conditions of Gardner–Gritzmann [R.J. Gardner, P. Gritzmann, Discrete tomography: Determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997) 2271–2295] can be performed in O(N4)-time.
File in questo prodotto:
File Dimensione Formato  
TCSBD08.pdf

non disponibili

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

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