A New Algorithm for the Computation of the Minkowski Difference of Convex Polyhedra

We present a new algorithm, based on the concept of contributing vertices, for the exact and efficient computation of the Minkowski difference of convex polyhedra. First, we extend the concept of contributing vertices for the Minkowski difference case. Then, we generate a Minkowski difference facets superset by exploiting the information provided by the computed contributing vertices. Finally, we compute the Minkowski difference polyhedron through the trimming of the generated superset. We compared our Contributing Vertices-based Minkowski Difference (CVMD) algorithm to a Nef polyhedra-based approach using Minkowski addition, complement, transposition, and union operations. The performance benchmark shows that our CVMD algorithm outperforms the indirect Nef polyhedra-based approach. All our implementations use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library.