next up previous contents index CD CD Algorithms
Next: Set and String Problems Up: Computational Geometry Previous: Maintaining Line Arrangements

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 tex2html_wrap_inline30580 ?

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 gif) 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 gif), 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 gif.   

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 tex2html_wrap_inline30590 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 gif), motion planning (see page gif), simplifying polygons (see page gif).      

next up previous contents index CD CD Algorithms
Next: Set and String Problems Up: Computational Geometry Previous: Maintaining Line Arrangements

Mon Jun 2 23:33:50 EDT 1997