Inner and outer approximations of polytopes using boxes

This paper deals with the problem of approximating a convex polytope in any finite dimension by a collection of (hyper)boxes. More exactly, given a polytope P by a system of linear inequalities, we look for two collections T and epsilon of boxes with non-overlapping interiors such that the union of all boxes in epsilon is contained in P and the union of all boxes in epsilon contains P. We propose and test several techniques to construct I and epsilon aimed at getting a good balance between two contrasting objectives: minimize the volume error and minimize the total number of generated boxes. We suggest how to modify the proposed techniques in order to approximate the projection of P onto a given subspace without computing the projection explicitly. (C) 2003 Elsevier B.V. All rights reserved.