The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Efi Fogel's Minkowski Sums and Collision Detection Software

Given two convex polygons with m and n vertices respectively, it was shown that detecting collision and computing directional penetration depth can be done in optimal time O(log m + log n) [GS88], and that the (absolute) penetration depth can be computed in O(log(m + n)) time using the Minkowski sum computed a priori [DHK93]. It is well known that the Minkowski sum in this case consists of m + n edges when there are no degeneracies, and can be computed in linear time simply by merging the edges in slope order.

  • Download Files (local site)
  • Offical Site

    Problem Links

    Minkowski Sum (8)

    This page last modified on 2008-07-10 .