The authors study the following polyhedra reconstruction problem in dimensions $d=2,3$: Let $\mathcal{R}$ be a set consisting of finitely many pairs $(v,k)$ where $v$ is a non-zero vector in $\mathbb{R}^d$ and $k$ is an integer. Here it is assumed that no two directions are linearly dependent. For such a set $\mathcal{R}$ and an integer $N$ the reconstruction problem consists of finding a polyhedron in $d$-space of size $N$, i.e., number of $(d-1)$-faces, such that for every pair $(v,k)\in \mathcal{R}$, the number of $(d-1)$-faces which are visible in the direction $v$ is exactly $k$. Their main results are: For $d=2$ the authors present an $O(|\mathcal{R}|+N)$ algorithm for an ordered set $\mathcal{R}$ (with respect to the directions). Moreover, if $N$ is not given they present an algorithm to find the minimum and maximum size polygon meeting the requirements of $\mathcal{R}$. The running time is roughly $O(|\mathcal{R}|\log |\mathcal{R}|)$. In the case $d=3$ it is shown that, in general, the problem becomes NP-hard when all the directions are not contained in at most two planes.
Martin Henk (Magdeburg)