Minkowski Sum of Polytopes Defined by Their Vertices

Vincent Delos, Denis Teissandier

University of Bordeaux, CNRS, National Center for French Research, I2M, UMR 5295, Talence, France.

DOI: 10.4236/jamp.2015.31008                

Abstract

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.

Keywords

Computational Geometry, Polytope, Minkowski Sum, Linear Programming, Convex Hull

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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.