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\} ?

Implementations

  • David Eppstein's Knuth-Morris-Pratt Algorithm and Minkowski sum code (C++) (rating 4)

    Related Problems

  • Motion Planning
  • Simplifying Polygons
  • Medial-Axis Transformation

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .