## Point-based Minkowski Sum Boundary

#### Jyh-Ming Lien

##### Overview

Minkowski sum is a fundamental operation in many geometric applications, including robotics, penetration depth estimation, solid modeling, and virtual prototyping. In this work, we propose to represent the boundary of the Minkowski sum approximately**using only points**. Our results show that this point-based representation can be generated efficiently. An important feature of our method is its straightforward implementation and parallelization.

##### Benefits of point-based Minkowski sum

- efficiency,
- robustness (can even work for non-manifold models with open surfaces),
- easy implementation (i.e., no convex decomposition and no need to perform union),
- easy parallelization,
- multiresolution representations, and
- similar functionality as mesh-based representations

##### Publications

Jyh-Ming Lien. "**Covering Minkowski Sum Boundary Using Points with Applications**", Computer Aided Geometric Design (CAGD), Volume 25, Issue 8, November 2008, Pages 652–666.

[pdf]

Jyh-Ming Lien. "

**Point-Based Minkowski Sum Boundary**", Proceedings of the Pacific Conference on Computer Graphics and Applications (Pacific Graphics), Maui, Hawaii, Nov. 2007, page 261--270.

[pdf]

##### Related Work

(If mesh-based representation is prefer, you may be more interested in this work.)##### Software

- Source code and pre-compiled binary can be found on the Software page

##### Examples

Input models: dancing children+unit cube | Minkowski sum |

Input models: pig+path | Minkowski sum |

Input models: baby+torus | Minkowski sum |

Input models: hooks | Minkowski sum |

Input models: octpus+(-dragon) | Minkowski sum |

##### Related Links

- Definition of Minkowski sum from the Stony Brook algorithm repository or Wikipedia
- Video on exact Minkowski sum and its applications (see this page by Dan Halperin et al.)
- Approximate Minkowski sum by Gokul Varadhan, Dinesh Manocha
- CGAL 3D Minkowski Sum of Polyhedra by Peter Hachenberger

List of MASC Research Pages