How Many Points Can Be Reconstructed from k Projections?
Jiřı́ Matoušek, Aleš Přívětivý, Petr Škovroň · SIAM Journal on Discrete Mathematics · 2008
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 “cube” 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).