The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.16 Minkowski Sum

Problem Input | Problem Output

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: The Computational Geometry Algorithms Library (C++) (rating 10)
  • Efi Fogel's Minkowski Sums and Collision Detection Software (Binary) (rating 8)
  • BIPM -- Bipartite Matching Codes (C++) (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 Transformation



    This page last modified on 2008-07-10 .
    www.algorist.com