The MinkSum program takes as input the vertices of a set of polytopes and outputs the vertices of their Minkowski sum. It is based on an algorithm of Komei Fukuda.
I have published a conference paper on the implementation:
Weibel, C. "Implementation & parallelization of a reverse-search algorithm for Minkowski sums".
In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX 2010), pp. 34-42.
[Bibtex]
David Eppstein praised the talk in his blog!
Download the latest version (1.8)
Previous versions probably will not work if your compiler is recent:
Download the latest version (1.7)
Download version (1.6.2)
Download the floating-point version (1.6.2f)
Normally, MINKSUM uses GMP to execute computations in exact precision. This ensures a stable program and exact results. The disadvantages of using floating-points for computations is that the program might crash, loop infinitely or even give wrong results. The advantage is that it is a lot faster (about 20 times). It seems rather stable, however. If your instances are relatively simple, you might be interested by this version.
Benjamin Kern has written a python interface to the library!
It is available on his web page.
The program should be compiled by typing "./configure" and "make" in the main directory of the archive. The executables are then found in the src/ directory. The program is run by typing
./minkSum [options] < input-file > output-file
so that the input is read from stdin and the output is written to stdout.
Here are the options:
-h or --help
print this help message
-c
write also the normal cone of vertices of the solution. Slower.
-s
write only vertices coordinates of the solution.
-n N
for minkSumFork and minkSumForkGrid, compute the sum in parallel using N processes
-d
write debug information to stderr.
-m
mute. Don't write anything to stderr
-p
ignore vertices who don't have a positive maximizer