Implementation and Parallelization of a Reverse-Search Algorithm for Minkowski Sums
Christophe Weibel · Society for Industrial and Applied Mathematics eBooks · 2010
We present an implementation of a reverse-search algorithm of Fukuda for computing Minkowski sums of polytopes efficiently. The algorithm allows summing any number of polytopes in any dimension, and is complete in the sense that it does not assume general position. Its running time depends linearly on the size of the output. To the best of our knowledge, this is the only existing implementation that can efficiently compute Minkowski sums in higher dimensions. The implementation uses the exact arithmetic GMP, which ensures robustness of the program and exactness of the results. We furthermore present a parallel version of our implementation to demonstrate the simplicity and efficiency of performing the reverse search in parallel. The results of the performance tests show a near-linear acceleration of our parallel implementation.