Quelltext der Seite Minkowski-Summe

Die '''Minkowski-Summe''' (nach [[Hermann Minkowski]]) zweier [[Teilmenge]]n <math>A</math> und <math>B</math> eines [[Vektorraum]]s 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 [[Lineare Algebra|linearen Algebra]] und der [[Funktionalanalysis]] kann dies jedoch zu Verwechslungen mit der [[Direkte Summe|direkten Summe]] führen.

Anwendungen findet die Minkowski-Summe zum Beispiel in der 2D- und 3D-[[Computergrafik]] und [[Bildverarbeitung]] (speziell [[Mathematische Morphologie|Morphologie]]; wird dort allerdings meist binäre Dilation oder [[Dilatation (Bildverarbeitung)|Dilatation]] genannt. Das Gegenstück ist die [[Erosion (Bildverarbeitung)|Erosion]]), in der [[Lineare Optimierung|linearen Optimierung]] (zum Beispiel Minkowski-Summe eines [[Polytop (Geometrie)|Polytop]]s und eines [[Kegel (Lineare Algebra)|Polyederkegels]]), in der Funktionalanalysis und in der [[Roboter]]steuerung.

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 [[Assoziativgesetz|assoziativ]], [[Kommutativgesetz|kommutativ]] und [[Distributivgesetz|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> <!-- (''[[Dreiecksungleichung]]'') -->, denn jedes Element wird mit jedem addiert und mehrfache Summen befinden sich nur einmal in der Menge.

Die Minkowski-Summe aus [[konvexe Menge|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>:
:<math>A = \{(1,0), (0,1), (0,-1)\}, B = \{(0,0), (1,1), (1,-1)\}</math>

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

Dann ist die Minkowski-Summe von A und B:
:<math>A + B = \{(1,0),(2,1),(2,-1), (0,1),(1,2),(1,0), (0,-1),(1,0),(1,-2)\}</math>
Der Punkt (1,0) kommt dreifach vor, d.&nbsp;h.
:<math>A + B = \{(1,0), (2,1), (2,-1), (0,1), (1,2), (0,-1), (1,-2)\}</math>

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 ==
* [http://demonstrations.wolfram.com/TheMinkowskiSumOfTwoTriangles/ Demonstration der Minkowski-Summe] (englisch)
* [http://www.cut-the-knot.org/Curriculum/Geometry/PolyAddition.shtml Applet zur Demonstration der Minkowski-Summe] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Lineare Algebra]]
[[Kategorie:Hermann Minkowski als Namensgeber]]