Name
Abstract | ||
|---|---|---|
. This paper deals with the problem of projecting polytopes in finite-dimensional 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 show that maximizing the volume of the orthogonal
projection on hyperplanes is already NP-hard for simplices. For minimization, the problem is easy for simplices but NP-hard for bipyramids over parallelotopes. Similar results are given for projections on lower-dimensional subspaces. Several
other related NP-hardness results are also proved including one for inradius computation of zonotopes and another for a location problem.
On the positive side, we present various polynomial-time approximation algorithms. In particular, we give a randomized algorithm
for maximizing orthogonal projections of CH-polytopes in R
n
on hyperplanes with an error bound of essentially . |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s004540010029 | Discrete & Computational Geometry |
Keywords | Field | DocType |
euclidean space,randomized algorithm,decision problem,computational complexity,orthogonal projection | Discrete mathematics,Projection (mathematics),Topology,Approximation algorithm,Combinatorics,Orthographic projection,Linear subspace,Euclidean space,Polytope,Euclidean geometry,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
24 | 2-3 | 0179-5376 |
Citations | PageRank | References |
2 | 0.38 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Burger | 1 | 2 | 0.38 |
| Peter Gritzmann | 2 | 412 | 46.93 |