Minkowski-Summe

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.

DefinitionBearbeiten

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.[1] 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.

EigenschaftenBearbeiten

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.

BeispielBearbeiten

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.

   

WeblinksBearbeiten

EinzelnachweiseBearbeiten

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