Details:
Title  From the zonotope construction to the Minkowski addition of convex polytopes  Author(s)  Komei Fukuda  Type  Article in Journal  Abstract  A zonotope is the Minkowski addition of line segments in Rd. The zonotope construction problem is to list all extreme points of a zonotope given by its line segments. By duality, it is equivalent to the arrangement construction problem—that is, to generate all regions of an arrangement of hyperplanes. By replacing line segments with convex Vpolytopes, we obtain a natural generalization of the zonotope construction problem: the construction of the Minkowski addition of k polytopes. Gritzmann and Sturmfels studied this general problem in various aspects and presented polynomial algorithms for the problem when one of the parameters k or d is fixed. The main objective of the present work is to introduce an efficient algorithm for variable d and k. Here we call an algorithm efficient or polynomial if it runs in time bounded by a polynomial function of both the input size and the output size. The algorithm is a natural extension of a known algorithm for the zonotope construction, based on linear programming and reverse search. It is compact, highly parallelizable and very easy to implement. This work has been motivated by the use of polyhedral computation for optimal tolerance determination in mechanical engineering.  Keywords  Convex polytope, Minkowski addition, Efficient algorithm, Reverse search  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717104000409 
Language  English  Journal  Journal of Symbolic Computation  Volume  38  Number  4  Pages  1261  1272  Year  2004  Note  Symbolic Computation in Algebra and Geometry  Edition  0  Translation 
No  Refereed 
No 
