An Efficient Algorithm to Calculate the Minkowski Sum of Convex 3D Polyhedra

Henk Bekker, Jos B.T.M. Roerdink

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

18 Citations (Scopus)
231 Downloads (Pure)

Abstract

A new method is presented to calculate the Minkowski sum of two convex polyhedra A and B in 3D. 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.
Original languageEnglish
Title of host publicationEPRINTS-BOOK-TITLE
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages10
Publication statusPublished - 2001

Cite this