Minkowski Sum of Polytopes Defined by Their Vertices

DOI: 10.4236/jamp.2015.31008   PDF   HTML   XML   5,126 Downloads   5,533 Views   Citations


Minkowski sums are of theoretical interest and have applications in fields related to industrial backgrounds. In this paper we focus on the specific case of summing polytopes as we want to solve the tolerance analysis problem described in [1]. Our approach is based on the use of linear programming and is solvable in polynomial time. The algorithm we developed can be implemented and parallelized in a very easy way.

Share and Cite:

Delos, V. and Teissandier, D. (2015) Minkowski Sum of Polytopes Defined by Their Vertices. Journal of Applied Mathematics and Physics, 3, 62-67. doi: 10.4236/jamp.2015.31008.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Teissandier, D., Delos, V. and Couetard, Y. (1999) Operations on Polytopes: Application to Tolerance Analysis. 6th CIRP Seminar on CAT, Enschede, Netherlands, 425-433.
[2] Homri, L., Teissandier, D. and Ballu, A. (2013) Tole-rancing Analysis by Operations on Polytopes. Design and Modeling of Mechanical Systems, Djerba (Tunisia), 597, 604.
[3] Srinivasan, V. (1993) Role of Sweeps in Tolerancing Semantics. ASME Proc. of the International Forum on Dimensional Tolerancing and Metrology, TS172.I5711, CRTD, Vol. 27, 69-78.
[4] Fukuda, K. (2004) From the Zonotope Construction to the Minkowski Addition of Convex Polytopes. Journal of Symbolic Computation, 38, 1261-1272, http://dx.doi.org/10.1016/j.jsc.2003.08.007
[5] Fukuda, K. and Weibel, C. (2005) Computing all Faces of the Minkowski Sum of V-Polytopes. Proceedings of the 17th Canadian Conference on Computational Geometry, 253-256,
[6] Teissandier, D. and Delos, V. (2011) Algorithm to Calculate the Minkowski Sums of 3-Polytopes Based on Normal Fans. Computer-Aided Design, 43, 1567-1576, http://dx.doi.org/10.1016/j.cad.2011.06.016
[7] Delos, V. and Teissandier, D. (2015) Minkowski Sum of -Polytopes in . Proceedings of the 4th Annual International Conference on Computational Mathematics, Computational Geometry and Statistics, Singapore.
[8] Fukuda, K. (2004) Frequently Asked Questions in Polyhedral Computation. Swiss Federal Institute of Technology Lausanne and Zurich, Switzerland.
[9] Weibel, C. (2007) Minkowski Sums of Polytopes. PhD Thesis, EPFL.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.