Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleFrom the zonotope construction to the Minkowski addition of convex polytopes
Author(s) Komei Fukuda
TypeArticle in Journal
AbstractA 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 V-polytopes, 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.
KeywordsConvex polytope, Minkowski addition, Efficient algorithm, Reverse search
URL http://www.sciencedirect.com/science/article/pii/S0747717104000409
JournalJournal of Symbolic Computation
Pages1261 - 1272
NoteSymbolic Computation in Algebra and Geometry
Translation No
Refereed No