# 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.

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. | |

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. | |

2D Minkowski Sum We present a method that efficiently computes the Minkowski sum boundary of two polygons using the notion of a reduced convolution. | |

Polygon Configuration Space Mapping We have developed a new method for constructing the boundary of the C-space obstacles (C-obst) of polygons. | |

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. | |

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