In 1903 Minkowski showed that, given pairwise different unit vectors u(1),.
..,u(m) in Euclidean n-space R-n which span R-n, and positive reals u(1),..
.,u(m) such that Sigma(t-1)(m) u(i) u(i) = 0, there exists a polytope P in
R-n, unique up to translation, with outer unit facet normals u(1),...,u(m)
and corresponding facet volumes u(1),...,u(m). This paper deals with the co
mputational complexity of the underlying reconstruction problem, to determi
ne a presentation of P as the intersection of its facet halfspaces. After a
natural reformulation that reflects the fact that the binary Turing-machin
e model of computation is employed, it is shown that this reconstruction pr
oblem can be solved in polynomial time when the dimension is fixed but is #
P-hard when the dimension is part of the input.
The problem of 'Minkowski reconstruction' has various applications in image
processing, and the underlying data structure is relevant for other algori
thmic questions in computational convexity.