Die Minkowski-Summe (nach Hermann Minkowski) zweier Teilmengen und eines Vektorraums ist die Menge, deren Elemente Summen von je einem Element aus und einem Element aus sind.
Definition Bearbeiten
Seien zwei Teilmengen eines Vektorraums. Dann ist die Minkowski-Summe definiert durch
Teilweise wird die Minkowski-Summe auch mit dem -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.
Eigenschaften Bearbeiten
Die Minkowski-Summe ist assoziativ, kommutativ und distributiv bezüglich der Vereinigung von Mengen, das heißt .
Für die Mächtigkeit der Minkowski-Summe gilt , 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 Bearbeiten
Gegeben A und B mit Elementen aus :
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.
Weblinks Bearbeiten
- Demonstration der Minkowski-Summe (englisch)
- Applet zur Demonstration der Minkowski-Summe (englisch)
Einzelnachweise Bearbeiten
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf: Computational Geometry: Algorithms and Applications. Springer-Verlag.