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.