Computer Science – Computational Complexity
Scientific paper
2008-04-25
Computer Science
Computational Complexity
Scientific paper
We study the projection of polytopes along $k$ orthogonal vectors for various input and output forms. We show that if $k$ is part of the input and we are interested in output-sensitive algorithms, then in most forms the problem is equivalent to enumerating vertices of polytopes, except in two where it is NP-hard. In two other forms the problem is trivial. We also review the complexity of computing projections when the projection directions are picked at random. For full-dimensional polytopes containing origin in the interior, projection is an operation dual to intersecting the polytope with a suitable hyperplane and so the results in this paper can be dualized by interchanging vertices with facets and projection with intersection. We would like to remark that even though most of the results in this paper do not appear to have been published before, they follow from straighforward reductions to other known results. The purpose of this paper is to serve as a reference to these results about the computational complexity of projection of polytopes onto affine subspaces.
No associations
LandOfFree
On Computing the Shadows and Slices of Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Computing the Shadows and Slices of Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Computing the Shadows and Slices of Polytopes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-728205