miniatura|La figura vermella és la suma de Minkowski de les figures blava i verda. En matemàtiques, la suma de dos subconjunts i d'un grup abelià (additiu) es forma sumant cada element d' a cada element de :
En geometria, l'addició de Minkowski de dos subconjunts i d'un espai euclidià és el conjunt dels punts els vectors de posició dels quals formen el conjunt suma dels vectors de posició d' i La suma de Minkowski depèn de l'elecció d'un origen a l'espai euclidià. Com que un canvi d'origen equival a traslladar la suma de Minkowski, la suma de Minkowski es defineix fins a una translació, i la seva forma i orientació estan ben definides.
La diferència de Minkowski (també subtracció de Minkowski, descomposició de Minkowski o diferència geomètrica) és la inversa corresponent, on produeix un conjunt que es podria sumar amb B per recuperar A. Això es defineix com el complement de la suma de Minkowski del complement d' A amb la reflexió de B al voltant de l'origen.
Aquesta definició permet una relació simètrica entre la suma i la diferència de Minkowski. Cal tenir en compte que prendre alternativament la suma i la diferència amb B no és necessàriament equivalent. La suma pot omplir buits que la diferència pot no tornar a obrir, i la diferència pot esborrar petites illes que la suma no pot recrear del no-res.
En el processament digital d'imatges 2D, la suma i la diferència de Minkowski es coneixen com a dilatació i erosió.
De vegades s'utilitza una definició alternativa de la diferència de Minkowski per calcular la intersecció de formes convexes. Això no és equivalent a la definició anterior i no és la inversa de l'operació de suma. En canvi, substitueix la suma vectorial de la suma de Minkowski per una subtracció vectorial. Si les dues formes convexes s'intersequen, el conjunt resultant contindrà l'origen.
El concepte rep el nom de Hermann Minkowski.
Exemple miniatura|Suma de Minkowski Per exemple, si tenim dos conjunts A i B, cadascun format per tres vectors de posició (informalment, tres punts), que representen els vèrtexs de dos triangles de , amb coordenades
i
aleshores la seva suma de Minkowski és
que comprèn els vèrtexs d'un hexàgon i el seu centre.
Per a la suma de Minkowski, el zero set, que conté només el vector zero, 0, és un element neutre: per a cada subconjunt S d'un espai vectorial,
El conjunt buit és important en la suma de Minkowski, perquè el conjunt buit aniquila tots els altres subconjunts: per a cada subconjunt S d'un espai vectorial, la seva suma amb el conjunt buit és buida:
Per a un altre exemple, considerem les sumes de Minkowski de pilotes obertes o tancades al camp que són o bé els nombres reals o bé els nombres complexos . If és la bola tancada de radi centrada a en aleshores per a qualsevol , i també es complirà per a qualsevol escalar tal que el producte està definit (cosa que passa quan or ). If , , i són tots diferents de zero, llavors les mateixes igualtats encara es mantindrien si s'hagués definit com la bola oberta, en lloc de la bola tancada, centrada a 0 (la suposició diferent de zero és necessària perquè la bola oberta de radi 0 és el conjunt buit). La suma de Minkowski d'una bola tancada i una bola oberta és una bola oberta. Més generalment, la suma de Minkowski d'un subconjunt obert amb qualsevol altre conjunt serà un subconjunt obert.
Si és el gràfic de i si i és el eix dins aleshores la suma de Minkowski d'aquests dos subconjunts tancats del pla és el conjunt obert que consisteix en tot el que no sigui el -eix. Això demostra que la suma de Minkowski de dos conjunts tancats no és necessàriament un conjunt tancat. Tanmateix, la suma de Minkowski de dos subconjunts tancats serà un subconjunt tancat si almenys un d'aquests conjunts també és un subconjunt compacte.
Casques convexes de sumes de Minkowski L'addició de Minkowski es comporta bé respecte a l'operació de prendre envolupants convexos, tal com es mostra a la següent proposició:
Aquest resultat es compleix més generalment per a qualsevol col·lecció finita de conjunts no buits:
En terminologia matemàtica, les operacions de suma de Minkowski i de formació d'embolcalls convexos són operacions de commutació.Theorem 3 (pages 562–563): For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196):
Si és un conjunt convex, aleshores també és un conjunt convex; a més a més
per a cada . Per contra, si aquesta "propietat distributiva" es compleix per a tots els nombres reals no negatius, i , aleshores el conjunt és convex.Chapter 1: miniatura|Un exemple d'un conjunt no convex tal que La figura de la dreta mostra un exemple d'un conjunt no convex per al qual
Un exemple en una dimensió és: Es pot calcular fàcilment que però per tant, de nou
Les sumes de Minkowski actuen linealment sobre el perímetre de cossos convexos bidimensionals: el perímetre de la suma és igual a la suma dels perímetres. A més, si és (l'interior de) una corba d'amplada constant, aleshores la suma de Minkowski de i de la seva rotació de 180° és un disc. Aquests dos fets es poden combinar per donar una demostració breu del teorema de Barbier sobre el perímetre de corbes d'amplada constant.The Theorem of Barbier (Java) at cut-the-knot.
Aplicacions L'addició de Minkowski juga un paper central en la morfologia matemàtica. Sorgeix en el paradigma de pinzell i traç dels gràfics per ordinador 2D (amb diversos usos, en particular per Donald E. Knuth a Metafont), i com l'operació d'escombrat sòlid dels gràfics per ordinador 3D. També s'ha demostrat que està estretament relacionada amb l'distància del vehicle de moviment de la Terra i, per extensió, amb el transport òptim.
Planificació de moviments Les sumes de Minkowski s'utilitzen en la planificació del moviment d'un objecte entre obstacles. S'utilitzen per al càlcul de l'espai de configuració, que és el conjunt de totes les posicions admissibles de l'objecte. En el model simple del moviment de translació d'un objecte en el pla, on la posició d'un objecte es pot especificar de manera única mitjançant la posició d'un punt fix d'aquest objecte, l'espai de configuració és la suma de Minkowski del conjunt d'obstacles i l'objecte mòbil situat a l'origen i girat 180 graus.
Mecanitzat per control numèric (NC) En el mecanitzat per control numèric, la programació de l'eina NC explota el fet que la suma de Minkowski de la peça de tall amb la seva trajectòria dóna la forma del tall en el material.
Modelatge sòlid 3D A OpenSCAD, les sumes de Minkowski s'utilitzen per perfilar una forma amb una altra forma, creant una combinació d'ambdues formes.
Teoria d'agregació Les sumes de Minkowski també s'utilitzen amb freqüència en la teoria d'agregació quan els objectes individuals que s'han d'agregar es caracteritzen mitjançant conjunts.
Detecció de col·lisions Les sumes de Minkowski, concretament les diferències de Minkowski, s'utilitzen sovint juntament amb els algoritmes GJK per calcular la detecció de col·lisions per a embolics convexos en motors de física.
Algoritmes per calcular sumes de Minkowski alt=Minkowski addition of four line-segments. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. The right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.|miniatura|Suma de Minkowski i envolupes convexes. Els setze punts de color vermell fosc (a la dreta) formen la suma de Minkowski dels quatre conjunts no convexos (a l'esquerra), cadascun dels quals consisteix en un parell de punts vermells. Les seves envolupes convexes (ombrejades en rosa) contenen signes més (+): El signe més de la dreta és la suma dels signes més de l'esquerra.
Cas planar Dos polígons convexos en el pla Per a dos polígons convexos i en el pla amb i vèrtexs, la seva suma de Minkowski és un polígon convex amb com a màxim + vèrtexs i es pot calcular en temps O( + ) mitjançant un procediment molt senzill, que es pot descriure informalment de la següent manera. Suposem que les arestes d'un polígon estan donades i la direcció, per exemple, en sentit antihorari, al llarg del límit del polígon. Aleshores es veu fàcilment que aquestes arestes del polígon convex estan ordenades per angle polar. Fusionem les seqüències ordenades de les arestes dirigides de i en una única seqüència ordenada Imaginem que aquestes arestes són fletxes sòlides que es poden moure lliurement mentre es mantenen paral·leles a la seva direcció original. Munteu aquestes fletxes en l'ordre de la seqüència unint la cua de la fletxa següent al cap de la fletxa anterior. Resulta que la cadena poligonal resultant serà de fet un polígon convex que és la suma de Minkowski de i
Suma essencial de Minkowski També hi ha una noció de la suma essencial de Minkowski +e de dos subconjunts de l'espai euclidià. La suma habitual de Minkowski es pot escriure com
Així, la suma essencial de Minkowski es defineix per
on μ denota la mesura de Lebesgue n-dimensional. La raó del terme "essencial" és la següent propietat de les funcions indicadores: mentre
es pot veure que
on "és sup" denota el supremum essencial.
Referències
Categoria:Geometria convexa Categoria:Algorismes