Minkowski-som

De minkowski-som van twee deelverzamelingen ${\displaystyle A}$ en ${\displaystyle B}$ van een vectorruimte, is de verzameling die bestaat uit de sommen van elk element uit ${\displaystyle A}$ met elk element uit ${\displaystyle B.}$ Voor de minkowski-som gebruikt men gewoonlijk het symbool ${\displaystyle \oplus ,}$ hoewel dit in de algebra verwarring kan geven met het symbool voor de directe som. De minkowski-som is genoemd naar de Duitse wiskundige Hermann Minkowski.

Links: een verzameling ${\displaystyle A}$
midden: Minkowski-som ${\displaystyle A\oplus A}$
rechts: "gewone" som ${\displaystyle A+A=2A}$

Definitie

Laat ${\displaystyle A}$ en ${\displaystyle B}$ deelverzamelingen zijn van de vectorruimte ${\displaystyle V.}$ De minkowski-som van ${\displaystyle A}$ en ${\displaystyle B}$ is

${\displaystyle A\oplus B=\{a+b\mid a\in A,b\in B\}}$

Eigenschappen

De minkowski-som is

• commutatief: ${\displaystyle A\oplus B=B\oplus A}$
• associatief: ${\displaystyle A\oplus (B\oplus C)=(A\oplus B)\oplus C}$

en heeft een

• neutraal element, het singleton ${\displaystyle \{0\}}$ met als element de nulvector: ${\displaystyle A\oplus \{0\}=A}$

De minkowski-som is distributief ten opzichte van de vereniging:

${\displaystyle A\oplus (B\cup C)=(A\oplus B)\cup (A\oplus C)}$

De minkowski-som van convexe verzamelingen is een convexe verzameling.

Voorbeelden

In twee dimensies stellen vectoren punten voor in het euclidische vlak. De verzamelingen ${\displaystyle A}$ en ${\displaystyle B}$ kunnen dan losse puntenverzamelingen zijn of compacte, al dan niet samenhangende deelverzamelingen van het vlak: lijnstukken, curven, convexe of concave veelhoeken enzovoort.

Als ${\displaystyle A=\{a\}}$ een singleton is, komt de minkowski-som ${\displaystyle A\oplus B}$ neer op de translatie van ${\displaystyle B}$ over de vector ${\displaystyle a.}$

Stel ${\displaystyle A}$ is een driehoek met als hoekpunten (0,-1), (0,1) en (1,0) en B is een andere driehoek met hoekpunten (0,0), (1,-1) en (1,1). De minkowski-som van de hoekpunten van A en B is de verzameling met zeven punten {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)} (dubbele sommen komen slechts eenmaal voor). Deze punten vormen een zeshoek met een zevende punt in het midden, zie de figuren hieronder:

• 
  verzameling ${\displaystyle A}$
• 
  verzameling ${\displaystyle B}$
• 
  Minkowski-som van ${\displaystyle A}$ en ${\displaystyle B}$

Minkowski-som van een curve met een cirkel

Alle andere punten van de minkowski-som ${\displaystyle A\oplus B}$ liggen binnen deze zeshoek. De minkowski-som van ${\displaystyle A}$ en ${\displaystyle B}$ is dus de zeshoek in de rechtse figuur. Er geldt algemeen, dat de minkowski-som van twee polygonen een polygoon is. Dit is geldig voor polyeders in willekeurige dimensies.

Grafische constructie

De minkowski-som van twee convexe verzamelingen kan men grafisch construeren: men neemt een van de verzamelingen en schuift die langs de rand van de tweede verzameling. Het oppervlak dat zo bestreken wordt, samen met het oppervlak van de tweede verzameling, is de minkowski-som. Stel dat de eerste verzameling een schijf is met middelpunt (0,0), dan bekomt men de minkowski-som van deze schijf met een andere convexe verzameling door de schijf met haar middelpunt op de rand van die verzameling te leggen en ze dan over de volledige rand van de verzameling te verschuiven. De figuur hiernaast illustreert dit principe met de minkowski-som van de gesloten blauwe lijn (die zelf geen convexe verzameling is) met een schijf waarvan de diameter gelijk is aan de breedte van de groene strook. De minkowski-som is in dit geval de verzameling van alle punten die op een afstand liggen van de lijn die kleiner of gelijk is aan de straal van de schijf. Punten in het rode gebied zijn op meer dan één manier de som van twee vectoren.

Als de tweede verzameling niet convex is, kan men trachten ze te verdelen in convexe deelverzamelingen; voor elke deelverzameling de minkowski-som bepalen op deze manier; en dan de vereniging nemen van die minkowski-sommen, steunend op de distributiviteit van minkowski-som en vereniging.^[1]

Toepassingen

De minkowski-som komt voor in velerlei takken van zuivere en toegepaste wiskunde. Enkele voorbeelden:

• In computer graphics, waar ze bekend is als dilatatie;
• In GIS-software voor het afbakenen van een perimeter: gegeven een ruimtelijk object zoals een perceel of het tracé van een weg of een pijpleiding, baken het gebied af tot op ${\displaystyle x}$ meter van dat object. Dat gebied is de minkowski-som van het object en een schijf met straal ${\displaystyle x}$;
• Bewegingsplanning in robotica, computergames en andere gebieden, bijvoorbeeld voor het bepalen van mogelijke routes van een robot in een omgeving met obstakels.

Externe links

• (en) Minkowski-som van een schijf en een polygoon (Wolfram Demonstrations Project)

Bronnen, noten en/of referenties

1. Pankaj K. Agarwal, Eyal Flato, Dan Halperin (2002). Polygon decomposition for efficient construction of Minkowski sums. Computational Geometry 21: 39-61 (Elsevier).