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