Minksum

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

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.

Release notes

    • 1.8: (2017-05-20) Modified to run with recent compilers. Works on my machine, but I'm still testing with various systems to check for surprises.
    • 1.7: Works with even more recent versions of gcc.
    • 1.6.2f: Uses floating-point numbers. Its seems stable, and is much faster, but it could well have stability issues.
    • 1.6.2: Fixed a compilation issue with recent versions of gcc. Many thanks go to Benjamin Kern and Johannes Rauh for their help with this. Also the configuration script now attempts to detect if GMP and CDD are already installed before compiling them
    • 1.6.1: Fixed a memory leak which could cause your computer to run out of memory on large computations
    • 1.6.0: Added parallel implementations

Python Numpy interface

Benjamin Kern has written a python interface to the library!

It is available on his web page.

How to use the program

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