WikiDer > Minkowski-Summe

Links: eine Sammlung ${Anzeigestil A}$
Mitte: Minkowski-Summe ${displaystyle Aoplus A}$
rechts: "normale" Summe" ${Anzeigestil A A=2A}$

Das minkowski-som von zwei Teilmengen${Anzeigestil A}$ und ${Anzeigestil B}$ von a Vektorraum, ist die Menge bestehend aus den Summen jedes Elements aus ${Anzeigestil A}$ mit jedem Element aus ${Anzeigestil B.}$ Für die Minkowski-Summe verwendet man normalerweise das Symbol ${displaystyle oplus ,}$ obwohl dies in der Algebra kann zu Verwechslungen mit dem Symbol für die direkte Summe. Die Minkowski-Summe ist nach dem Deutschen benannt MathematikerHermann Minkowski.

Definition

spät ${Anzeigestil A}$ und ${Anzeigestil B}$ sind Teilmengen des Vektorraums ${Displaystil V.}$ Das minkowski-som von ${Anzeigestil A}$ und ${Anzeigestil B}$ ist

${displaystyle Aoplus B={a bmid ain A,bin B}}$

Eigenschaften

Die Minkowski-Summe ist

• kommutativ: ${Anzeigestil Aoplus B=Boplus A}$
• assoziativ: ${Anzeigestil Aoplus (Boplus C) = (Aoplus B)oplus C}$

und hat ein

• neutrales Element, es Singleton${Anzeigestil {0}}$ mit dem Element des Nullvektors: ${displaystyle Aoplus {0}=A}$

Die Minkowski-Summe ist verteilend relativ zu Verband:

${Anzeigestil Aoplus (Bcup C)=(Aoplus B)cup (Aoplus C)}$

Die Minkowski-Summe von konvexe Sammlungen ist eine konvexe Menge.

Beispiele

In zwei Dimensionen repräsentieren Vektoren Punkte im euklidische Ebene. Die Kollektionen ${Anzeigestil A}$ und ${Anzeigestil B}$ können dann separate Punktmengen oder kompakt sein, unabhängig davon, ob zusammenhaltend Teilmengen der Ebene: Segmente, Kurven, konvex oder konkav Polygone und so weiter.

wenn ${Anzeigestil A={a}}$ ein Singleton ist, kommt die Minkowski-Summe ${displaystyle Aoplus B}$ unten auf dem Übersetzung von ${Anzeigestil B}$ über den Vektor ${Anzeigestil u.}$

Paar ${Anzeigestil A}$ ist ein Dreieck mit Ecken (0,-1), (0.1) und (1,0) und B ist ein weiteres Dreieck mit Ecken (0,0), (1,-1) und (1,1) . Die Minkowski-Summe der Ecken von A und B ist die Menge von sieben Punkten {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), ( 1 , 0), (0, −1), (1, 0), (1, −2)} (Doppelsummen kommen nur einmal vor). Diese Punkte bilden ein Sechseck mit einem siebten Punkt in der Mitte, siehe folgende Abbildungen:

• 

  Sammlung ${Anzeigestil A}$

• 

  Sammlung ${Anzeigestil B}$

• 

  Minkowski-Summe von ${Anzeigestil A}$ und ${Anzeigestil B}$

Minkowski-Summe einer Kurve mit einem Kreis

Alle anderen Punkte der Minkowski-Summe ${displaystyle Aoplus B}$ befinden sich in diesem Sechseck. Die Minkowski-Summe von ${Anzeigestil A}$ und ${Anzeigestil B}$ ist daher das Sechseck in der rechten Abbildung. Allgemein gilt, dass die Minkowski-Summe von zwei Polygone ist ein Polygon. Dies gilt für Polyeder in beliebigen Dimensionen.

Grafische Konstruktion

Die Minkowski-Summe zweier konvexer Mengen lässt sich grafisch konstruieren: man nimmt eine der Mengen und schiebt sie am Rand der zweiten Menge entlang. Die so abgedeckte Fläche ist zusammen mit der Fläche des zweiten Satzes die Minkowski-Summe. Angenommen, die erste Menge ist a Scheibe mit Mittelpunkt (0,0), dann erhält man die Minkowski-Summe dieser Scheibe mit einer anderen konvexen Menge, indem man die Scheibe mit ihrem Mittelpunkt auf den Rand dieser Menge legt und dann über den gesamten Rand der Menge verschiebt . Die nebenstehende Abbildung veranschaulicht dieses Prinzip mit der Minkowski-Summe der geschlossenen blauen Linie (die selbst keine konvexe Menge ist) mit einer Scheibe, deren Durchmesser gleich der Breite des grünen Streifens ist. Die Minkowski-Summe ist in diesem Fall die Menge aller Punkte, die einen Abstand von der Geraden kleiner oder gleich dem Radius der Scheibe haben. Punkte im roten Bereich sind in mehr als einer Hinsicht die Summe zweier Vektoren.

Wenn die zweite Menge nicht konvex ist, kann man versuchen, sie in konvexe Teilmengen zu unterteilen; Bestimmen Sie auf diese Weise die Minkowski-Summe für jede Teilmenge; und nehmen Sie dann die Vereinigung dieser Minkowski-Summen, wobei Sie sich auf die Distributivität von Minkowski-Summe und Vereinigung verlassen.^[1]

Anwendungen

Die Minkowski-Summe kommt in vielen Bereichen der reinen und angewandten Mathematik vor. Einige Beispiele:

• Im Computergrafik, wo sie bekannt ist als Erweiterung;
• Im GISPerimeterabgrenzungssoftware: Abgrenzen eines räumlichen Objekts wie eines Grundstücks oder der Trasse einer Straße oder einer Pipeline ${Anzeigestil x}$ Meter von diesem Objekt entfernt. Diese Fläche ist die Minkowski-Summe des Objekts und einer Scheibe mit Radius ${Anzeigestil x}$;
• Bewegungsplanung im Robotik, Computerspiele und andere Bereiche, beispielsweise zum Bestimmen möglicher Routen eines Roboters in einer Hindernisumgebung.

Externe Links

• (und) Minkowski-Summe einer Scheibe und eines Polygons (Wolfram Demonstrationsprojekt)