Equality Set Projection: A new algorithm for the projection of polytopes in halfspace representation

In this paper we introduce a new algorithm called Equality Set Projection (ESP) for computing the orthogonal projection of bounded, convex polytopes. Our solution addresses the case where the input polytope is represented as the intersection of a finite number of halfplanes and its projection is given in an irredundant halfspace form. Unlike many existing approaches, the key advantage offered by ESP is its output sensitivity, i.e., its complexity is a function of the number of facets in the projection of the polytope. This feature makes it particularly suited for many problems of theoretical and practical importance in which the number of vertices far exceeds the number of facets. Further, it is shown that for non-degenerate polytopes of fixed size (dimension and number of facets) the complexity is linear in the number of facets in the projection. Numerical results are presented that demonstrate that high dimensional polytopes can be projected efficiently.


Year:
2004
Publisher:
Cambridge, Cambridge University Engineering Dept
Laboratories:




 Record created 2011-10-25, last modified 2018-01-28

External link:
Download fulltext
Publisher's version
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)