Minkowski Sum


Minkowski sum is closely related to many applications such as motion planning, penetration depth estimation, and object containment. Therefore, its importance motivates us to find efficient algorithms to compute.

image Scaling Minkowski Sums
We present two methods for dynamically updating Minkowski sums under scaling, the first of which updates the sum under uniform scaling of arbitrary polygons and polyhedra, and the second of which updates the sum under non-uniform scaling of convex polyhedra.
image Generalized Minkowski Sum with Rotation
We developed a method that efficiently computes the Minkowski sums 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. We show that we can efficiently update, without complete re-computation, the Minkowski sums.
image 2D Minkowski Sum
We present a method that efficiently computes the Minkowski sum boundary of two polygons using the notion of a reduced convolution.
image Polygon Configuration Space Mapping
We have developed a new method for constructing the boundary of the C-space obstacles (C-obst) of polygons.
image 3D Minkowski Sum Made Simple
We propose a convolution based method to get Minkwoski sum boundary efficiently. It avoids computing the 3-d arrangement and the winding numbers.
image Point-based Minkowski Sum Boundary
We propose to represent the boundary of the Minkowski sum approximately with only points. It does not only provide similar functionality as mesh-based representation but also saves a lot of computation.

List of MASC Research Pages
Computer Science @ George Mason University