×

From the zonotope construction to the Minkowski addition of convex polytopes. (English) Zbl 1121.52020

Summary: 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)

Software:

CDDMEX; cdd
PDFBibTeX XMLCite
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, (7th CIRP International Seminar on Computer-Aided Tolerancing. 7th CIRP International Seminar on Computer-Aided Tolerancing, ENS de Cachan, France, April, 2001 (2001))
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.