Minkowski-Summe

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

Definition

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

<math>A + B := \{a+b\,|\,a \in A, b \in B\}</math>.

Teilweise wird die Minkowski-Summe auch mit dem <math>\oplus</math>-Zeichen anstatt mit dem normalen Pluszeichen notiert.<ref>Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf: Computational Geometry: Algorithms and Applications. Springer-Verlag.</ref> 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

<math>A - B := A + (-B)=\{a-b\,|\,a \in A, b \in B\}</math>.

Eigenschaften

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

Für die Mächtigkeit der Minkowski-Summe gilt <math>|A + B| \leq |A| \cdot |B|</math> , 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 <math>\mathbb R^2</math>:

Datei:Minkowski-sumex1.svg Datei:Minkowski-sumex2.svg

Dann ist die Minkowski-Summe von A und B:

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

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.

Datei:Minkowski-sumex3.svg Datei:Minkowski-sumex4.svg

Weblinks

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

Einzelnachweise