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
This page last modified on 2008-07-10
.
www.algorist.com
