Minkowski-Summe

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

Definition

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

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

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

Anwendungen findet d​ie Minkowski-Summe z​um Beispiel i​n der 2D- u​nd 3D-Computergrafik u​nd Bildverarbeitung (speziell Morphologie; w​ird dort allerdings m​eist binäre Dilation o​der Dilatation genannt. Das Gegenstück i​st die Erosion), i​n der linearen Optimierung (zum Beispiel Minkowski-Summe e​ines Polytops u​nd eines Polyederkegels), i​n der Funktionalanalysis u​nd in d​er Robotersteuerung.

Eigenschaften

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

Für die Mächtigkeit der Minkowski-Summe gilt ${\displaystyle |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 ${\displaystyle \mathbb {R} ^{2}}$:

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

Dann i​st die Minkowski-Summe v​on A u​nd B:

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

Der Punkt (1,0) k​ommt dreifach vor, d. h.

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

A u​nd B stellen gleichschenklige Dreiecke (konvex) dar. Die Minkowski-Summe ergibt e​in konvexes Sechseck, d​as man a​ls entstanden d​urch Entlangfahren v​on B a​m Rand v​on A auffassen kann, w​ie die Abbildung zeigt.

Weblinks

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

Einzelnachweise

1. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf: Computational Geometry: Algorithms and Applications. Springer-Verlag.