On the computational complexity of reconstructing lattice sets from their X-rays
Identifieur interne : 001364 ( Istex/Corpus ); précédent : 001363; suivant : 001365On the computational complexity of reconstructing lattice sets from their X-rays
Auteurs : R. J. Gardner ; P. Gritzmann ; D. PrangenbergSource :
- 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
Links to Exploration step
ISTEX:BB4BF7812D6BA72441A287FF36C966CC5E517306Le 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><affiliation><mods:affiliation>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>1 Supported in part by the Alexander von Humboldt Foundation and by U.S. National Science Foundation Grant DMS-9501289.</mods:affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation><mods:affiliation>University of Technology, Center for Mathematical Sciences, D-80290 Munich, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>2 Supported in part by a Max Planck Research Award and by the German Federal Ministery of Education, Science, Research and Technology Grant 03-GR7TM1.</mods:affiliation></affiliation></author><author><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name><affiliation><mods:affiliation>Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>3 Supported by the Deutsche Forschungsgemeinschaft through the ·Graduiertenkolleg Mathematische Optimierung’ at the Universität Trier.</mods:affiliation></affiliation></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></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><mods:affiliation>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>1 Supported in part by the Alexander von Humboldt Foundation and by U.S. National Science Foundation Grant DMS-9501289.</mods:affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation><mods:affiliation>University of Technology, Center for Mathematical Sciences, D-80290 Munich, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>2 Supported in part by a Max Planck Research Award and by the German Federal Ministery of Education, Science, Research and Technology Grant 03-GR7TM1.</mods:affiliation></affiliation></author><author><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name><affiliation><mods:affiliation>Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>3 Supported by the Deutsche Forschungsgemeinschaft through the ·Graduiertenkolleg Mathematische Optimierung’ at the Universität Trier.</mods: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><istex><corpusName>elsevier</corpusName><author><json:item><name>R.J. Gardner</name><affiliations><json:string>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA</json:string><json:string>1 Supported in part by the Alexander von Humboldt Foundation and by U.S. National Science Foundation Grant DMS-9501289.</json:string></affiliations></json:item><json:item><name>P. Gritzmann</name><affiliations><json:string>University of Technology, Center for Mathematical Sciences, D-80290 Munich, Germany</json:string><json:string>2 Supported in part by a Max Planck Research Award and by the German Federal Ministery of Education, Science, Research and Technology Grant 03-GR7TM1.</json:string></affiliations></json:item><json:item><name>D. Prangenberg</name><affiliations><json:string>Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany</json:string><json:string>3 Supported by the Deutsche Forschungsgemeinschaft through the ·Graduiertenkolleg Mathematische Optimierung’ at the Universität Trier.</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>05, 68R</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>68U</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>82D</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>90C</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>92C</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Tomography</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Discrete tomography</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>High resolution transmission electron microscopy</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Computational complexity</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Polynomial-time algorithm</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>NP-hardness</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>#P-hardness</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Lattice</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Data compression</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Image processing</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Data security</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><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.</abstract><qualityIndicators><score>6.512</score><pdfVersion>1.2</pdfVersion><pdfPageSize>468 x 684 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>16</keywordCount><abstractCharCount>855</abstractCharCount><pdfWordCount>9875</pdfWordCount><pdfCharCount>54230</pdfCharCount><pdfPageCount>27</pdfPageCount><abstractWordCount>126</abstractWordCount></qualityIndicators><title>On the computational complexity of reconstructing lattice sets from their X-rays</title><pii><json:string>S0012-365X(98)00347-1</json:string></pii><refBibs><json:item><author><json:item><name>R. Aharoni</name></json:item><json:item><name>G.T. Herman</name></json:item><json:item><name>A. Kuba</name></json:item></author><host><volume>171</volume><pages><last>16</last><first>1</first></pages><author></author><title>Discrete Math.</title></host><title>Binary vectors partially determined by linear equation systems</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>E. Barcucci</name></json:item><json:item><name>A. Del Lungo</name></json:item><json:item><name>M. Nivat</name></json:item><json:item><name>R. Pinzani</name></json:item></author><host><volume>155</volume><pages><last>347</last><first>321</first></pages><author></author><title>Thcoret. Comput. Sci.</title></host><title>Reconstructing convex polyominoes from their horizontal and vertical projections</title></json:item><json:item><author><json:item><name>G. Bianchi</name></json:item><json:item><name>M. Longinetti</name></json:item></author><host><volume>5</volume><pages><last>242</last><first>223</first></pages><author></author><title>Discrete Comput. Geom.</title></host><title>Reconstructing plane sets from projections</title></json:item><json:item><author><json:item><name>S.-K. Chang</name></json:item></author><host><volume>14</volume><pages><last>24</last><first>21</first></pages><author></author><title>Comm. ACM</title></host><title>The reconstruction of binary patterns from their projections</title></json:item><json:item><author><json:item><name>M. Dyer</name></json:item><json:item><name>R. Kannan</name></json:item><json:item><name>J. Mount</name></json:item></author><host><volume>10</volume><pages><last>506</last><first>487</first></pages><author></author><title>Random Structures Algorithms</title></host><title>Sampling contingency tables</title></json:item><json:item><author><json:item><name>P.C. Fishburn</name></json:item><json:item><name>J.C. Lagarias</name></json:item><json:item><name>J.A. Reeds</name></json:item><json:item><name>L.A. Shepp</name></json:item></author><host><volume>91</volume><pages><last>159</last><first>149</first></pages><author></author><title>Discrete Math.</title></host><title>Sets uniquely determined by projections on axes. II. Discrete case</title></json:item><json:item><author><json:item><name>P.C. Fishburn</name></json:item><json:item><name>P. Schwander</name></json:item><json:item><name>L.A. Shepp</name></json:item><json:item><name>J. Vanderbei</name></json:item></author><host><volume>75</volume><pages><last>62</last><first>39</first></pages><author></author><title>Discrete Appl. Math.</title></host><title>The discrete Radon transform and its approximate inversion via linear programming</title></json:item><json:item><author><json:item><name>R.J. Gardner</name></json:item><json:item><name>P. Gritzmann</name></json:item></author><host><volume>349</volume><pages><last>2295</last><first>2271</first></pages><author></author><title>Trans. Amer. Math. Soc.</title></host><title>Discrete tomography: determination of finite sets by X-rays</title></json:item><json:item><author><json:item><name>R.J. Gardner</name></json:item><json:item><name>P. Gritzmann</name></json:item><json:item><name>D. Prangenberg</name></json:item></author><host><pages><last>132</last><first>121</first></pages><author></author><title>Proc. Int. Symp. on Optical Science, Engineering, and Instrumentation, SPIE</title></host><title>On the reconstruction of binary images from their discrete Radon transforms</title></json:item><json:item><host><author></author><title>Computers and Intractability: A Guide to the Theory of NP-Completeness</title></host></json:item><json:item><author><json:item><name>J.J. Gerbrands</name></json:item><json:item><name>C.H. Slump</name></json:item></author><host><volume>18</volume><pages><last>36</last><first>18</first></pages><author></author><title>Comput. Graph. Image Process.</title></host><title>A network flow approach to reconstruction of the left ventricle from two projections</title></json:item><json:item><author><json:item><name>R. Gordon</name></json:item><json:item><name>G.T. Herman</name></json:item></author><host><volume>14</volume><pages><last>768</last><first>759</first></pages><author></author><title>Comm. ACM</title></host><title>Reconstruction of pictures from their projections</title></json:item><json:item><author><json:item><name>D. Gusfield</name></json:item></author><host><volume>17</volume><pages><last>571</last><first>552</first></pages><author></author><title>SIAM J. Comput.</title></host><title>A graph theoretic approach to statistical data security</title></json:item><json:item><author><json:item><name>R.W. Irving</name></json:item><json:item><name>M.R. Jerrum</name></json:item></author><host><volume>23</volume><pages><last>184</last><first>170</first></pages><author></author><title>SIAM J. Comput.</title></host><title>Three-dimensional statistical data security problems</title></json:item><json:item><author><json:item><name>D.S. Johnson</name></json:item></author><host><author></author><title>Handbook of Theoretical Computer Science</title></host><serie><author></author><title>Handbook of Theoretical Computer Science</title></serie><title>A catalog of complexity classes</title></json:item><json:item><author><json:item><name>C. Kisielowski</name></json:item><json:item><name>P. Schwander</name></json:item><json:item><name>F.H. Baumann</name></json:item><json:item><name>M. Seibt</name></json:item><json:item><name>Y. Kim</name></json:item><json:item><name>A. Ourmazd</name></json:item></author><host><volume>58</volume><pages><last>155</last><first>131</first></pages><author></author><title>Ultramicroscopy</title></host><title>An approach to quantitative high-resolution transmission electron microscopy of crystalline materials</title></json:item><json:item><author><json:item><name>D. Kölzow</name></json:item><json:item><name>A. Kuba</name></json:item><json:item><name>A. Volčič</name></json:item></author><host><volume>4</volume><pages><last>237</last><first>205</first></pages><author></author><title>Discrete Comput. Geom.</title></host><title>An algorithm for reconstructing convex bodies from their projections</title></json:item><json:item><author><json:item><name>A. Kuba</name></json:item></author><host><volume>27</volume><pages><last>265</last><first>249</first></pages><author></author><title>Comput. Vision, Graph. Image Process.</title></host><title>The reconstruction of two-directionally connected binary patterns from their two orthogonal projections</title></json:item><json:item><host><author></author><title>The Mathematics of Computerized Tomography</title></host></json:item><json:item><author><json:item><name>A. Rényi</name></json:item></author><host><volume>3</volume><pages><last>142</last><first>131</first></pages><author></author><title>Acta Math. Acad. Sci. Hung.</title></host><title>On projections of probability distributions</title></json:item><json:item><host><author></author><title>Combinatorial Mathematics</title></host></json:item><json:item><author><json:item><name>T.J. Schaefer</name></json:item></author><host><pages><last>226</last><first>216</first></pages><author></author><title>Proc. 10th Ann. ACM Symp. on Theory of Computing</title></host><title>The complexity of satisfiability problems</title></json:item><json:item><author><json:item><name>P. Schwander</name></json:item><json:item><name>C. Kisielowski</name></json:item><json:item><name>M. Seibt</name></json:item><json:item><name>F.H. Baumann</name></json:item><json:item><name>Y. Kim</name></json:item><json:item><name>A. Ourmazd</name></json:item></author><host><volume>71</volume><pages><last>4153</last><first>4150</first></pages><author></author><title>Phys. Rev. Lett.</title></host><title>Mapping projected potential, interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy</title></json:item><json:item><author><json:item><name>A. Shliferstein</name></json:item><json:item><name>Y.T. Chien</name></json:item></author><host><volume>10</volume><pages><last>340</last><first>327</first></pages><author></author><title>Pattern Recognition</title></host><title>Switching components and the ambiguity problem in the reconstruction of pictures from their projections</title></json:item><json:item><author><json:item><name>L.G. Valiant</name></json:item></author><host><volume>8</volume><pages><last>201</last><first>189</first></pages><author></author><title>Theoret. Comput. Sci.</title></host><title>The complexity of computing the permanent</title></json:item></refBibs><genre><json:string>research-article</json:string></genre><serie><volume>vol. A</volume><pages><last>161</last><first>67</first></pages><language><json:string>unknown</json:string></language><title>Handbook of Theoretical Computer Science</title></serie><host><volume>202</volume><pii><json:string>S0012-365X(00)X0058-1</json:string></pii><pages><last>71</last><first>45</first></pages><issn><json:string>0012-365X</json:string></issn><issue>1–3</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Discrete Mathematics</title><publicationDate>1999</publicationDate></host><categories><wos><json:string>science</json:string><json:string>mathematics</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>information & communication technologies</json:string><json:string>computation theory & mathematics</json:string></scienceMetrix></categories><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1016/S0012-365X(98)00347-1</json:string></doi><id>BB4BF7812D6BA72441A287FF36C966CC5E517306</id><score>0.35471368</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/BB4BF7812D6BA72441A287FF36C966CC5E517306/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/BB4BF7812D6BA72441A287FF36C966CC5E517306/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/BB4BF7812D6BA72441A287FF36C966CC5E517306/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">On the computational complexity of reconstructing lattice sets from their X-rays</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1999</date></publicationStmt><notesStmt><note type="content">Section title: Contributions</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">On the computational complexity of reconstructing lattice sets from their X-rays</title><author xml:id="author-1"><persName><forename type="first">R.J.</forename><surname>Gardner</surname></persName><affiliation>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA</affiliation><affiliation>1 Supported in part by the Alexander von Humboldt Foundation and by U.S. National Science Foundation Grant DMS-9501289.</affiliation></author><author xml:id="author-2"><persName><forename type="first">P.</forename><surname>Gritzmann</surname></persName><affiliation>University of Technology, Center for Mathematical Sciences, D-80290 Munich, Germany</affiliation><affiliation>2 Supported in part by a Max Planck Research Award and by the German Federal Ministery of Education, Science, Research and Technology Grant 03-GR7TM1.</affiliation></author><author xml:id="author-3"><persName><forename type="first">D.</forename><surname>Prangenberg</surname></persName><affiliation>Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany</affiliation><affiliation>3 Supported by the Deutsche Forschungsgemeinschaft through the ·Graduiertenkolleg Mathematische Optimierung’ at the Universität Trier.</affiliation></author></analytic><monogr><title level="j">Discrete Mathematics</title><title level="j" type="abbrev">DISC</title><idno type="pISSN">0012-365X</idno><idno type="PII">S0012-365X(00)X0058-1</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="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></monogr><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></fileDesc><profileDesc><creation><date>1999</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="keyword"><list><head>MSC</head><item><term>05, 68R</term></item><item><term>68U</term></item><item><term>82D</term></item><item><term>90C</term></item><item><term>92C</term></item></list></keywords></textClass><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Tomography</term></item><item><term>Discrete tomography</term></item><item><term>High resolution transmission electron microscopy</term></item><item><term>Computational complexity</term></item><item><term>Polynomial-time algorithm</term></item><item><term>NP-hardness</term></item><item><term>#P-hardness</term></item><item><term>Lattice</term></item><item><term>Data compression</term></item><item><term>Image processing</term></item><item><term>Data security</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1998-09-14">Modified</change><change when="1999">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/BB4BF7812D6BA72441A287FF36C966CC5E517306/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>DISC</jid><aid>98003471</aid><ce:pii>S0012-365X(98)00347-1</ce:pii><ce:doi>10.1016/S0012-365X(98)00347-1</ce:doi><ce:copyright type="unknown" year="1999"></ce:copyright></item-info><head><ce:dochead><ce:textfn>Contributions</ce:textfn></ce:dochead><ce:title>On the computational complexity of reconstructing lattice sets from their X-rays</ce:title><ce:author-group><ce:author><ce:given-name>R.J.</ce:given-name><ce:surname>Gardner</ce:surname><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="FN1"><ce:sup>1</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>P.</ce:given-name><ce:surname>Gritzmann</ce:surname><ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup></ce:cross-ref><ce:cross-ref refid="FN2"><ce:sup>2</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>D.</ce:given-name><ce:surname>Prangenberg</ce:surname><ce:cross-ref refid="AFF3"><ce:sup>c</ce:sup></ce:cross-ref><ce:cross-ref refid="FN3"><ce:sup>3</ce:sup></ce:cross-ref></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>University of Technology, Center for Mathematical Sciences, D-80290 Munich, Germany</ce:textfn></ce:affiliation><ce:affiliation id="AFF3"><ce:label>c</ce:label><ce:textfn>Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany</ce:textfn></ce:affiliation><ce:footnote id="FN1"><ce:label>1</ce:label><ce:note-para>Supported in part by the Alexander von Humboldt Foundation and by U.S. National Science Foundation Grant DMS-9501289.</ce:note-para></ce:footnote><ce:footnote id="FN2"><ce:label>2</ce:label><ce:note-para>Supported in part by a Max Planck Research Award and by the German Federal Ministery of Education, Science, Research and Technology Grant 03-GR7TM1.</ce:note-para></ce:footnote><ce:footnote id="FN3"><ce:label>3</ce:label><ce:note-para>Supported by the Deutsche Forschungsgemeinschaft through the ·Graduiertenkolleg Mathematische Optimierung’ at the Universität Trier.</ce:note-para></ce:footnote></ce:author-group><ce:date-received day="4" month="2" year="1998"></ce:date-received><ce:date-revised day="14" month="9" year="1998"></ce:date-revised><ce:date-accepted day="21" month="9" year="1998"></ce:date-accepted><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>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.</ce:simple-para><ce:simple-para>We completely settle the complexity status of the basic problems of existence (data consistency), uniqueness (determination), and reconstruction of finite subsets of the <ce:italic>d</ce:italic>-dimensional integer lattice <ce:italic>γ</ce:italic><ce:sup><ce:italic>d</ce:italic></ce:sup> 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 <ce:italic>d</ce:italic> ⩾ 2 and for a prescribed but arbitrary set of <ce:italic>m</ce:italic> ⩾ 2 pairwise nonparallel lattice directions, the problems are solvable in polynomial time if <ce:italic>m</ce:italic> = 2 and are NP-complete (or NP-equivalent) otherwise.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords class="msc"><ce:section-title>MSC</ce:section-title><ce:keyword><ce:text>05, 68R</ce:text></ce:keyword><ce:keyword><ce:text>68U</ce:text></ce:keyword><ce:keyword><ce:text>82D</ce:text></ce:keyword><ce:keyword><ce:text>90C</ce:text></ce:keyword><ce:keyword><ce:text>92C</ce:text></ce:keyword></ce:keywords><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Tomography</ce:text></ce:keyword><ce:keyword><ce:text>Discrete tomography</ce:text></ce:keyword><ce:keyword><ce:text>High resolution transmission electron microscopy</ce:text></ce:keyword><ce:keyword><ce:text>Computational complexity</ce:text></ce:keyword><ce:keyword><ce:text>Polynomial-time algorithm</ce:text></ce:keyword><ce:keyword><ce:text>NP-hardness</ce:text></ce:keyword><ce:keyword><ce:text>#P-hardness</ce:text></ce:keyword><ce:keyword><ce:text>Lattice</ce:text></ce:keyword><ce:keyword><ce:text>Data compression</ce:text></ce:keyword><ce:keyword><ce:text>Image processing</ce:text></ce:keyword><ce:keyword><ce:text>Data security</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>On the computational complexity of reconstructing lattice sets from their X-rays</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>On the computational complexity of reconstructing lattice sets from their X-rays</title></titleInfo><name type="personal"><namePart type="given">R.J.</namePart><namePart type="family">Gardner</namePart><affiliation>Department of Mathematics, Western Washington University, Bellingham, WA 98225-9063, USA</affiliation><affiliation>1 Supported in part by the Alexander von Humboldt Foundation and by U.S. National Science Foundation Grant DMS-9501289.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">P.</namePart><namePart type="family">Gritzmann</namePart><affiliation>University of Technology, Center for Mathematical Sciences, D-80290 Munich, Germany</affiliation><affiliation>2 Supported in part by a Max Planck Research Award and by the German Federal Ministery of Education, Science, Research and Technology Grant 03-GR7TM1.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">D.</namePart><namePart type="family">Prangenberg</namePart><affiliation>Fb IV, Mathematik, Universität Trier, D-54286 Trier, Germany</affiliation><affiliation>3 Supported by the Deutsche Forschungsgemeinschaft through the ·Graduiertenkolleg Mathematische Optimierung’ at the Universität Trier.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued><dateModified encoding="w3cdtf">1998-09-14</dateModified><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract 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.</abstract><note type="content">Section title: Contributions</note><subject><genre>MSC</genre><topic>05, 68R</topic><topic>68U</topic><topic>82D</topic><topic>90C</topic><topic>92C</topic></subject><subject><genre>Keywords</genre><topic>Tomography</topic><topic>Discrete tomography</topic><topic>High resolution transmission electron microscopy</topic><topic>Computational complexity</topic><topic>Polynomial-time algorithm</topic><topic>NP-hardness</topic><topic>#P-hardness</topic><topic>Lattice</topic><topic>Data compression</topic><topic>Image processing</topic><topic>Data security</topic></subject><relatedItem type="host"><titleInfo><title>Discrete Mathematics</title></titleInfo><titleInfo type="abbreviated"><title>DISC</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">19990506</dateIssued></originInfo><identifier type="ISSN">0012-365X</identifier><identifier type="PII">S0012-365X(00)X0058-1</identifier><part><date>19990506</date><detail type="volume"><number>202</number><caption>vol.</caption></detail><detail type="issue"><number>1–3</number><caption>no.</caption></detail><extent unit="issue pages"><start>1</start><end>299</end></extent><extent unit="pages"><start>45</start><end>71</end></extent></part></relatedItem><identifier type="istex">BB4BF7812D6BA72441A287FF36C966CC5E517306</identifier><identifier type="DOI">10.1016/S0012-365X(98)00347-1</identifier><identifier type="PII">S0012-365X(98)00347-1</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001364 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001364 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|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. |  |