Minkowski Sum

  

 

Input description: Point sets or polygons A and B, with n and m vertices, respectively.

Problem description: What is the convolution of A and B, i.e. the Minkowski sum ?

Discussion: 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 (see Section ) 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 (see Section ), 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.      

The definition of Minkowski sum assumes that the polygons A and B have been positioned on a coordinate system:

where x+y is the vector sum of two points. Thinking of this in terms of translation, the Minkowski sum is the union of all translations of A by a point defined within B. Issues arising in computing Minkowski sums include:  

• Are your objects rasterized images or explicit polygons? - The definition of Minkowski summation suggests a simple algorithm if A and B are rasterized images, and thus contain a number of pixels proportional to their area. Initialize a sufficiently large matrix of pixels by determining the size of the convolution of the bounding boxes of A and B. For each pair of points in A and B, sum up their coordinates and darken the appropriate pixel. These algorithms get somewhat more complicated if an explicit polygonal representation of the Minkowski sum is needed.   
• Are your objects convex or nonconvex? - The complexity of computing Minkowski sum depends in a serious way on the shape of the polygons. If both A and B are convex, the Minkowski sum can be found in O(n+m) time by tracing the boundary of one polygon with another. If one of them is nonconvex, the size of the sum alone can be as large as . Even worse is when both A and B are nonconvex, in which case the size of the sum can be as large as . Be aware that the Minkowski sum of nonconvex polygons can have a certain ugliness to it. For example, holes can be either created or destroyed.  

Although more efficient algorithms exist, a straightforward approach to computing the Minkowski sum is based on triangulation and union. First, triangulate both polygons, then compute the Minkowski sum of each triangle of A against each triangle of B. The sum of a triangle against another triangle is easy to compute and is a special case of convex polygons, discussed below. The union of these O(n m) convex polygons will be A+B. Algorithms for computing the union of polygons are based on plane sweep, as discussed in Section .   

Computing the Minkowski sum of two convex polygons is easier than the general case, because the sum will always be convex. For convex polygons, it is easiest to slide A along the boundary of B and compute the sum edge by edge. This is the best approach for triangles against triangles as well.

Implementations: To date, we have not uncovered a suitable Minkowski sum code. When we do, it will be made available on http://www.cs.sunysb.edu/ algorith, the Algorithm Repository site.

Notes: Good expositions on algorithms for Minkowski sums include [O'R94]. The fastest algorithms for various cases of Minkowski sums include [KOS91, Sha87]. Kedem and Sharir [KS90] present an efficient algorithm for translational motion planning for polygonal robots, based on Minkowski sums.

Related Problems: Thinning (see page ), motion planning (see page ), simplifying polygons (see page ).