Computational complexity of three-dimensional discrete tomography with missing data

Kei Kimura, Takuya Kamehashi

Research output: Contribution to journalArticlepeer-review


Discrete tomography deals with problems of determining shape of a discrete object from a set of projections. In this paper, we deal with a fundamental problem in discreet tomography: reconstructing a discrete object in R3 from its orthogonal projections, which we call three-dimensional discrete tomography. This problem has been mostly studied under the assumption that complete data of the projections are available. However, in practice, there might be missing data in the projections, which come from, e.g., the lack of precision in the measurements. In this paper, we consider the three-dimensional discrete tomography with missing data. Specifically, we consider the following three fundamental problems in discrete tomography: the consistency, counting, and uniqueness problems, and classify the computational complexities of these problems in terms of the length of one dimension. We also generalize these results to higher-dimensional discrete tomography, which has applications in operations research and statistics.

Original languageEnglish
Pages (from-to)823-858
Number of pages36
JournalJapan Journal of Industrial and Applied Mathematics
Issue number3
Publication statusPublished - Sept 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Engineering
  • Applied Mathematics


Dive into the research topics of 'Computational complexity of three-dimensional discrete tomography with missing data'. Together they form a unique fingerprint.

Cite this