DYMSUM: Dynamic Minkowski Sum

Emily Behar, Jyh-Ming Lien

In this work, we developed a method that efficiently computes the Minkowski sum of rotating convex polyhedra. It is well known that the Minkowski sum of two polyhedra can be dramatically different from the Minkowski sum of the same polyhedra after rotation. To the best of our knowledge, all existing methods recompute a new Minkowski sum every time when the input polyhedra rotates. A main problem of recomputing the Minkowski sum from scratch is that it requires the same computation even when a small amount of rotation is applied. Computing the Minkowski sum of polyhedra undergoing small rotations can be found in many problems, such as general penetration depth estimation for physically-based simulation and configuration-space obstacle approximation for robotic motion planning.


Dynamic Minkowski Sum of Convex Shapes, Emily Behar and Jyh-Ming Lien, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), May 2011
Web Site / Paper (pdf) / BibTeX

Minkowski Sums of Rotating Convex Polyhedra, Jyh-Ming Lien, Proceedings of the ACM Symposium on Computational Geometry (SoCG), College Park, Maryland. Video Abstract, Jun. 2008.
Full text: Proceedings (pdf) Video (divx.avi)

Technical Reports
Dynamic Minkowski Sum of Convex Shapes, Emily Behar, Jyh-Ming Lien, Department of Computer Science, George Mason University, (Technical Report), 2010
Web Site / Paper (pdf) / BibTeX

List of MASC Research Pages
Computer Science @ George Mason University