Finding optimal shadows of polytopes

This paper deals with the problem of projecting polytopes in finite-dimensi onal Euclidean spaces on subspaces of given dimension so as to maximize or minimize the volume of the projection. As to the computational complexity of the underlying decision problems we s how that maximizing the volume of the orthogonal projection on hyperplanes is already, NP-hard for simplices. For minimization, the problem is easy fo r simplices but NP-hard for bipyramids over parallelotopes. Similar results are given for projections on lower-dimensional subspaces. Several other re lated NP-hardness results are also proved including one for inradius comput ation of zonotopes and another for a location problem. On the positive side, we present various polynomial-time approximation algo rithms. In particular, we give a randomized algorithm for maximizing orthog onal projections of H-polytopes in R-n on hyperplanes with an error bound o f essentially O(root n/logn).