Robust polyhedral Minkowski sums with GPU implementation

• We compute Minkowski sum boundaries of two input polyhedra.
• Sum polygons from convolution are created, subdivided, and traversed for boundary construction.
• The algorithm is robustly implemented on CPU and GPU both.
• The performance on GPU is orders-of-magnitude higher than previous works.

We present a Minkowski sum algorithm for polyhedra based on convolution. We develop robust CPU and GPU implementations, using our ACP strategy to eliminate degeneracy and to enforce a user-specified backward error bound. We test the programs on 45 inputs with an error bound of 10−810−8. The CPU program outperforms prior work, including non-robust programs. The GPU program using 2688 CUDA cores exhibits a median speedup factor of 36, which increases to 68 on the 6 hardest tests. For example, it computes a Minkowski sum with a million features in 20 seconds.