Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set

This paper addresses methods for finding a rectangle of minimum area which encloses the projection of a given convex set in a higher dimensional space onto the plane of the rectangle. For a polytope, a parametric simplex algorithm is proposed for obtaining a global solution. The average number of pivots required by this algorithm is polynomial in the size of the linear system. For a nonlinear convex set, it is shown that a successive underestimation method generates an •-global solution in finite time.