On the computational complexity of reconstructing lattice sets from their X-rays
Identifieur interne : 002076 ( Main/Exploration ); précédent : 002075; suivant : 002077On the computational complexity of reconstructing lattice sets from their X-rays
Auteurs : R. J. Gardner [États-Unis] ; P. Gritzmann [Allemagne] ; D. Prangenberg [Allemagne]Source :
- Discrete Mathematics [ 0012-365X ] ; 1999.
Abstract
We study the computational complexity of various inverse problems in discrete tomography. These questions are motivated by demands from the material sciences for the reconstruction of crystalline structures from images produced by quantitative high resolution transmission electron microscopy. We completely settle the complexity status of the basic problems of existence (data consistency), uniqueness (determination), and reconstruction of finite subsets of the d-dimensional integer lattice γd that are only accessible via their line sums (discrete X-rays) in some prescribed finite set of lattice directions. Roughly speaking, it turns out that for all d ⩾ 2 and for a prescribed but arbitrary set of m ⩾ 2 pairwise nonparallel lattice directions, the problems are solvable in polynomial time if m = 2 and are NP-complete (or NP-equivalent) otherwise.
Url:
DOI: 10.1016/S0012-365X(98)00347-1
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001364
- to stream Istex, to step Curation: 001252
- to stream Istex, to step Checkpoint: 000D25
- to stream Main, to step Merge: 002430
- to stream Main, to step Curation: 002076
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>On the computational complexity of reconstructing lattice sets from their X-rays</title><author><name sortKey="Gardner, R J" sort="Gardner, R J" uniqKey="Gardner R" first="R. J." last="Gardner">R. J. Gardner</name></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name></author><author><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:BB4BF7812D6BA72441A287FF36C966CC5E517306</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0012-365X(98)00347-1</idno><idno type="url">https://api.istex.fr/document/BB4BF7812D6BA72441A287FF36C966CC5E517306/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001364</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001364</idno><idno type="wicri:Area/Istex/Curation">001252</idno><idno type="wicri:Area/Istex/Checkpoint">000D25</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000D25</idno><idno type="wicri:doubleKey">0012-365X:1999:Gardner R:on:the:computational</idno><idno type="wicri:Area/Main/Merge">002430</idno><idno type="wicri:Area/Main/Curation">002076</idno><idno type="wicri:Area/Main/Exploration">002076</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">On the computational complexity of reconstructing lattice sets from their X-rays</title><author><name sortKey="Gardner, R J" sort="Gardner, R J" uniqKey="Gardner R" first="R. J." last="Gardner">R. J. Gardner</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063</wicri:regionArea><placeName><region type="state">Washington (État)</region></placeName></affiliation><affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>University of Technology, Center for Mathematical Sciences, D-80290 Munich</wicri:regionArea><wicri:noRegion>80290 Munich</wicri:noRegion><wicri:noRegion>D-80290 Munich</wicri:noRegion></affiliation><affiliation></affiliation></author><author><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fb IV, Mathematik, Universität Trier, D-54286 Trier</wicri:regionArea><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>D-54286 Trier</wicri:noRegion></affiliation><affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Discrete Mathematics</title><title level="j" type="abbrev">DISC</title><idno type="ISSN">0012-365X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">202</biblScope><biblScope unit="issue">1–3</biblScope><biblScope unit="page" from="45">45</biblScope><biblScope unit="page" to="71">71</biblScope></imprint><idno type="ISSN">0012-365X</idno></series><idno type="istex">BB4BF7812D6BA72441A287FF36C966CC5E517306</idno><idno type="DOI">10.1016/S0012-365X(98)00347-1</idno><idno type="PII">S0012-365X(98)00347-1</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0012-365X</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study the computational complexity of various inverse problems in discrete tomography. These questions are motivated by demands from the material sciences for the reconstruction of crystalline structures from images produced by quantitative high resolution transmission electron microscopy. We completely settle the complexity status of the basic problems of existence (data consistency), uniqueness (determination), and reconstruction of finite subsets of the d-dimensional integer lattice γd that are only accessible via their line sums (discrete X-rays) in some prescribed finite set of lattice directions. Roughly speaking, it turns out that for all d ⩾ 2 and for a prescribed but arbitrary set of m ⩾ 2 pairwise nonparallel lattice directions, the problems are solvable in polynomial time if m = 2 and are NP-complete (or NP-equivalent) otherwise.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>États-Unis</li></country><region><li>Washington (État)</li></region></list><tree><country name="États-Unis"><region name="Washington (État)"><name sortKey="Gardner, R J" sort="Gardner, R J" uniqKey="Gardner R" first="R. J." last="Gardner">R. J. Gardner</name></region></country><country name="Allemagne"><noRegion><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name></noRegion><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002076 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002076 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:BB4BF7812D6BA72441A287FF36C966CC5E517306
|texte= On the computational complexity of reconstructing lattice sets from their X-rays
}}
| This area was generated with Dilib version V0.6.31. |  |