  We present an efficient algorithm that computes the Minkowski sum of two
polygons, which may have holes. The new algorithm is based on the convolution
approach. Its efficiency stems in part from a property for Minkowski sums of
polygons with holes, which in fact holds in any dimension: Given two polygons
with holes, for each input polygon we can fill up the holes that are relatively
small compared to the other polygon. Specifically, we can always fill up all
the holes of at least one polygon, transforming it into a simple polygon, and
still obtain exactly the same Minkowski sum. Obliterating holes in the input
summands speeds up the computation of Minkowski sums.
  We introduce a robust implementation of the new algorithm, which follows the
Exact Geometric Computation paradigm and thus guarantees exact results. We also
present an empirical comparison of the performance of Minkowski sum
construction of various input examples, where we show that the implementation
of the new algorithm exhibits better performance than several other
implementations in many cases. In particular, we compared the implementation of
the new algorithm, an implementation of the standard convolution algorithm, and
an implementation of the decomposition approach using various convex
decomposition methods, including two new methods that handle polygons with
holes - one is based on vertical decomposition and the other is based on
triangulation.
  The software has been developed as an extension of the "2D Minkowski Sums"
package of CGAL (Computational Geometry Algorithms Library). Additional
information and supplementary material is available at our project page
http://acg.cs.tau.ac.il/projects/rc
