Minkowski-som

De minkowski-som van twee deelverzamelingen en van een vectorruimte, is de verzameling die bestaat uit de sommen van elk element uit met elk element uit Voor de minkowski-som gebruikt men gewoonlijk het symbool 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
midden: Minkowski-som
rechts: "gewone" som

DefinitieBewerken

Laat   en   deelverzamelingen zijn van de vectorruimte   De minkowski-som van   en   is

 

EigenschappenBewerken

De minkowski-som is

  • commutatief:  
  • associatief:  

en heeft een

  • neutraal element, het singleton   met als element de nulvector:  

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

 

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

VoorbeeldenBewerken

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

Als   een singleton is, komt de minkowski-som   neer op de translatie van   over de vector  

Stel   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:

 
Minkowski-som van een curve met een cirkel

Alle andere punten van de minkowski-som   liggen binnen deze zeshoek. De minkowski-som van   en   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 constructieBewerken

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]

ToepassingenBewerken

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   meter van dat object. Dat gebied is de minkowski-som van het object en een schijf met straal  ;
  • Bewegingsplanning in robotica, computergames en andere gebieden, bijvoorbeeld voor het bepalen van mogelijke routes van een robot in een omgeving met obstakels.

Externe linksBewerken