From the zonotope construction to the Minkowski addition of convex polytopes.

*(English)*Zbl 1121.52020Summary: A zonotope is the Minkowski addition of line segments in \(\mathbb R^d\). 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.

##### MSC:

52A39 | Mixed volumes and related topics in convex geometry |

52B55 | Computational aspects related to convexity |

68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |

PDF
BibTeX
XML
Cite

\textit{K. Fukuda}, J. Symb. Comput. 38, No. 4, 1261--1272 (2004; Zbl 1121.52020)

Full Text:
DOI

##### References:

[1] | Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete comput. geom., 8, 295-313, (1992) · Zbl 0752.68082 |

[2] | Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete appl. math., 65, 21-46, (1996) · Zbl 0854.68070 |

[3] | Ferrez, J.; Fukuda, K.; Liebling, T.M., Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, European J. oper. res., (2003), (in press) · Zbl 1066.90101 |

[4] | Fukuda, K.; Ferrez, J., 2002. implementations of LP-based reverse search algorithms for the zonotope construction and the fixed-rank convex quadratic maximization in binary variables using the zram and the cddlib libraries |

[5] | Giordano, M.; Kataya, B.; Pairel, E., Tolerance analysis and synthesis by means of clearance and deviation spaces, () |

[6] | Gritzmann, P.; Sturmfels, B., Minkowski addition of polytopes: computational complexity and applications to GrĂ¶bner bases, SIAM J. discrete math., 6, 246-269, (1993) · Zbl 0798.68157 |

[7] | Seymour, P., A note on hyperplane generation, J. combin. theory ser. B, 61, 88-91, (1994) · Zbl 0803.05015 |

[8] | Sturmfels, B., Polynomial equations and convex polytopes, Amer. math. monthly, 105, 10, 907-922, (1998) · Zbl 0988.52021 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.