The reconstruction of an unknown function $f$ from its line sums is the aim of discrete tomography. However, two main aspects prevent reconstruction from being an easy task. In general, many solutions are allowed due to the presence of the switching functions. Even when uniqueness conditions are available, results about the NP-hardness of reconstruction algorithms make their implementation inefficient when the values of $f$ are in certain sets. We show that this is not the case when $f$ takes values in a field or a unique factorization domain, such as $R$ or $Z$. We present a linear time reconstruction algorithm (in the number of directions and in the size of the grid), which outputs the original function values for all points outside of the switching domains. Freely chosen values are assigned to the other points, namely, those with ambiguities. Examples are provided.

Ceko, M., Pagani, S. M. C., Tijdeman, R., Algorithms for linear time reconstruction by discrete tomography II, <<DISCRETE APPLIED MATHEMATICS>>, 2021; 298 (N/A): 7-20. [doi:10.1016/j.dam.2021.03.008] [http://hdl.handle.net/10807/177553]

Algorithms for linear time reconstruction by discrete tomography II

Pagani, Silvia Maria Carla;
2021

Abstract

The reconstruction of an unknown function $f$ from its line sums is the aim of discrete tomography. However, two main aspects prevent reconstruction from being an easy task. In general, many solutions are allowed due to the presence of the switching functions. Even when uniqueness conditions are available, results about the NP-hardness of reconstruction algorithms make their implementation inefficient when the values of $f$ are in certain sets. We show that this is not the case when $f$ takes values in a field or a unique factorization domain, such as $R$ or $Z$. We present a linear time reconstruction algorithm (in the number of directions and in the size of the grid), which outputs the original function values for all points outside of the switching domains. Freely chosen values are assigned to the other points, namely, those with ambiguities. Examples are provided.
Inglese
Ceko, M., Pagani, S. M. C., Tijdeman, R., Algorithms for linear time reconstruction by discrete tomography II, <<DISCRETE APPLIED MATHEMATICS>>, 2021; 298 (N/A): 7-20. [doi:10.1016/j.dam.2021.03.008] [http://hdl.handle.net/10807/177553]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/10807/177553
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 3
social impact