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