Stony Brook Algorithm Repository


Minkowski Sum

Input
Output

Input Description: Point sets or polygons \(A\) and \(B\), with \(n\) and \(m\) vertices, respectively.
Problem: What is the convolution of \(A\) and \(B\), ie. the Minkowski sum \(A+B = \{x+y| x\in A, y \in B\}\)?

Excerpt from The Algorithm Design Manual: Minkowski sums are useful geometric operations that can be used to fatten objects in appropriate ways. For example, a popular approach to motion planning for polygonal robots in a room with polygonal obstacles fattens each of the obstacles by taking the Minkowski sum of them with the shape of the robot. This reduces the problem to moving a point from the start to the goal using a standard shortest-path algorithm. Another application is in shape simplification where we fatten the boundary of an object to create a channel and then define as the shape the minimum link path lying within this channel. Similarly, convolving an irregular object with a small circle will help smooth out the boundaries by eliminating minor nicks and cuts.


Implementations

cgal (rating 10)
CGAL (rating 10)
Efi Fogel's Minkowski Sums and Collision Detection Software (rating 8)
convex-minkowski-sum (rating 5)
BIPM (rating 4)


Recommended Books

Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke

Related Problems


Motion Planning

Simplifying Polygons

Medial-Axis Transform

Go To Main Page