{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:41:55Z","timestamp":1787323315477,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Let A be an n-point set in the plane. A discrete X-ray of A in direction u gives the number of points of A on each line parallel to u. We define $F(k)$ as the maximum number n such that there exist k directions $u_1,\\dots,u_k$ such that every set of at most n points in the plane can be uniquely reconstructed from its discrete X-rays in these directions. A simple \u201ccube\u201d construction shows $F(k)\\le2^{k-1}$. We establish the lower bound $F(k)\\ge2^{\\Omega(k\/\\log k)}$ by reducing the problem through linear algebra to a graph-theoretic question, for which we then obtain an almost tight bound. As a part of the proof we establish a result in extremal theory that allows one to conclude that, under certain conditions, a graph has only at most a logarithmic density, which may be of independent interest. We also improve the upper bound to $F(k)\\le O(1.81712^k)$ (or $O(1.79964^k)$ if we allow A to be a multiset).<\/jats:p>","DOI":"10.1137\/080715706","type":"journal-article","created":{"date-parts":[[2008,10,17]],"date-time":"2008-10-17T18:04:21Z","timestamp":1224266661000},"page":"1605-1623","source":"Crossref","is-referenced-by-count":9,"title":["How Many Points Can Be Reconstructed from\n                    <i>k<\/i>\n                    Projections?"],"prefix":"10.1137","volume":"22","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ale\u0161","family":"P\u0159\u00edv\u011btiv\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"\u0160kovro\u0148","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,10,17]]},"reference":[{"key":"R1","unstructured":"N. Alon,\n                      A note on network reliability\n                      , in Discrete Probability and Algorithms, IMA Vol. Math. Appl. 72, D. Aldous, P. Diaconis, J. Spencer, and J. M. Steele, eds., Springer-Verlag, Berlin, 1995, pp. 11\u201314."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(01)00431-1"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187787"},{"key":"R4","unstructured":"N. Biggs,\n                      Algebraic Graph Theory\n                      , 2nd ed., Cambridge University Press, Cambridge, 1993."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/040621375"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-97-01741-8"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187842"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. J. Gardner,\n                      Geometric Tomography\n                      , 2nd ed., Western Washington University, Bellingham, 2006.","DOI":"10.1017\/CBO9781107341029"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020535"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.2307\/27641956"},{"key":"R11","unstructured":"\u0160. Holub,\n                      private communication\n                      , 2003."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02022515"},{"key":"R13","unstructured":"G. T\u00f3th,\n                      private communication\n                      (through A. P\u00f3r), 2003."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080715706","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:54:45Z","timestamp":1787320485000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080715706"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/080715706"],"URL":"https:\/\/doi.org\/10.1137\/080715706","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}