Minkowski-Summe

Die Minkowski-Summe (nach Hermann Minkowski) zweier Teilmengen $A$ und $B$ eines Vektorraums ist die Menge, deren Elemente Summen von je einem Element aus $A$ und einem Element aus $B$ sind.

Definition

Seien $A,B\subset V$ zwei Teilmengen eines Vektorraums. Dann ist die Minkowski-Summe definiert durch

$A+B:=\{a+b\,|\,a\in A,b\in B\}$.

Teilweise wird die Minkowski-Summe auch mit dem $\oplus$-Zeichen anstatt mit dem normalen Pluszeichen notiert. Im Bereich der linearen Algebra und der Funktionalanalysis kann dies jedoch zu Verwechslungen mit der direkten Summe führen.

Anwendungen findet die Minkowski-Summe zum Beispiel in der 2D- und 3D-Computergrafik und Bildverarbeitung (speziell Morphologie; wird dort allerdings meist binäre Dilation oder Dilatation genannt. Das Gegenstück ist die Erosion), in der linearen Optimierung (zum Beispiel Minkowski-Summe eines Polytops und eines Polyederkegels), in der Funktionalanalysis und in der Robotersteuerung.

Analog definiert man die Minkowski-Differenz

$A-B:=A+(-B)=\{a-b\,|\,a\in A,b\in B\}$.

Eigenschaften

Die Minkowski-Summe ist assoziativ, kommutativ und distributiv bezüglich der Vereinigung von Mengen, das heißt $A+(B\cup C)=(A+B)\cup (A+C)$.

Für die Mächtigkeit der Minkowski-Summe gilt $|A+B|\leq |A|\cdot |B|$ , denn jedes Element wird mit jedem addiert und mehrfache Summen befinden sich nur einmal in der Menge.

Die Minkowski-Summe aus konvexen Mengen ist wieder eine konvexe Menge. Bei konvexen Mengen kann die Berechnung der Minkowski-Summe auch sehr leicht grafisch erfolgen: Man schiebt ein Polytop auf dem Rand des anderen entlang und der überdeckte Bereich ist die Minkowski-Summe.

Beispiel

Gegeben A und B mit Elementen aus $\mathbb {R} ^{2}$:

$A=\{(1,0),(0,1),(0,-1)\},B=\{(0,0),(1,1),(1,-1)\}$

Dann ist die Minkowski-Summe von A und B:

$A+B=\{(1,0),(2,1),(2,-1),(0,1),(1,2),(1,0),(0,-1),(1,0),(1,-2)\}$

Der Punkt (1,0) kommt dreifach vor, d. h.

$A+B=\{(1,0),(2,1),(2,-1),(0,1),(1,2),(0,-1),(1,-2)\}$

A und B stellen gleichschenklige Dreiecke (konvex) dar. Die Minkowski-Summe ergibt ein konvexes Sechseck, das man als entstanden durch Entlangfahren von B am Rand von A auffassen kann, wie die Abbildung zeigt.

Weblinks

• Demonstration der Minkowski-Summe (englisch)
• Applet zur Demonstration der Minkowski-Summe (englisch)