An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra
Henk Bekker and Jos B. T. M. Roerdink. An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra. In: Proc. Computational Science - ICCS 2001, Lecture Notes in Computer Science 2074, V. N. Alexandrov, J. J. Dongarra, B. A. Juliano, R. S. Renner and C. J. Kenneth Tan (eds.), Springer, 2001, pp. 619-628 (Part I).
A new method is presented to calculate the Minkowski sum of two convex polyhedra A and B in 3D. The method works as follows. The slope diagrams of A and B are considered as graphs. These graphs are given edge attributes. From these attributed graphs the attributed graph of the Minkowski sum is constructed. This graph is then transformed into the Minkowski sum of A and B. The running time of the algorithm is linear in the number of edges of the Minkowski sum.
Download in gzipped postscript format