Back
 JAMP  Vol.3 No.1 , January 2015
Minkowski Sum of Polytopes Defined by Their Vertices
Vincent Delos, Denis Teissandier
Show more
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
Cite this paper: 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.
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.

 
 
Top