Adición de Minkowski

Suma los conjuntos de vectores A y B sumando cada vector de A a cada vector de B

La cifra roja es la suma de Minkowski de las cifras azules y verdes.

En geometría , la suma de Minkowski de dos conjuntos de vectores de posición A y B en el espacio euclidiano se forma sumando cada vector de A a cada vector de B :

${\displaystyle A+B=\{\mathbf {a} +\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in B\}}$

La diferencia de Minkowski ( también resta de Minkowski , descomposición de Minkowski o diferencia geométrica ) ^[1] es la inversa correspondiente, donde produce un conjunto que podría sumarse con B para recuperar A. Este se define como el complemento de la suma de Minkowski del complemento de A con la reflexión de B sobre el origen. ^[2] ${\displaystyle (A-B)}$

${\displaystyle -B=\{\mathbf {-b} \,|\,\mathbf {b} \in B\}}$

${\displaystyle A-B=(A^{\complement }+(-B))^{\complement }}$

Esta definición permite una relación simétrica entre la suma y la diferencia de Minkowski. Tenga en cuenta que tomar alternativamente la suma y la diferencia con B no es necesariamente equivalente. La suma puede llenar vacíos que la diferencia tal vez no vuelva a abrir, y la diferencia puede borrar pequeñas islas que la suma no puede recrear de la nada.

${\displaystyle (A-B)+B\subseteq A}$

${\displaystyle (A+B)-B\supseteq A}$

${\displaystyle A-B=(A^{\complement }+(-B))^{\complement }}$

${\displaystyle A+B=(A^{\complement }-(-B))^{\complement }}$

En el procesamiento de imágenes 2D , la suma y diferencia de Minkowski se conocen como dilatación y erosión .

A veces se utiliza una definición alternativa de la diferencia de Minkowski para calcular la intersección de formas convexas. ^[3] Esto no es equivalente a la definición anterior y no es una operación inversa de la operación de suma. En su lugar, reemplaza la suma vectorial de la suma de Minkowski con una resta vectorial . Si las dos formas convexas se cruzan, el conjunto resultante contendrá el origen.

${\displaystyle A-B=\{\mathbf {a} -\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in B\}=A+(-B)}$

El concepto lleva el nombre de Hermann Minkowski .

Ejemplo

Suma de Minkowski A + B

Por ejemplo, si tenemos dos conjuntos A y B , cada uno de los cuales consta de tres vectores de posición (informalmente, tres puntos), que representan los vértices de dos triángulos en , con coordenadas ${\displaystyle \mathbb {R} ^{2}}$

${\displaystyle A=\{(1,0),(0,1),(0,-1)\}}$

y

${\displaystyle B=\{(0,0),(1,1),(1,-1)\}}$

entonces su suma de Minkowski es

${\displaystyle A+B=\{(1,0),(2,1),(2,-1),(0,1),(1,2),(1,0),(0,-1),(1,0),(1,-2)\},}$

que comprende los vértices de un hexágono y su centro.

Para la suma de Minkowski, el conjunto cero , que contiene sólo el vector cero , 0, es un elemento identidad : para cada subconjunto S de un espacio vectorial, ${\displaystyle \{0\},}$

${\displaystyle S+\{0\}=S.}$

El conjunto vacío es importante en la suma de Minkowski, porque el conjunto vacío aniquila todos los demás subconjuntos: para cada subconjunto S de un espacio vectorial, su suma con el conjunto vacío es vacía:

${\displaystyle S+\emptyset =\emptyset .}$

Para otro ejemplo, considere las sumas de Minkowski de bolas abiertas o cerradas en el campo , que son números reales o números complejos. Si la bola cerrada de radio está centrada en entonces para cualquier y también se cumplirá para cualquier escalar tal que el producto sea definido (lo que sucede cuando o ). Si y son todos distintos de cero, entonces se mantendrían las mismas igualdades si se hubiera definido como la bola abierta, en lugar de la bola cerrada, centrada en (la suposición distinta de cero es necesaria porque la bola abierta de radio es el conjunto vacío) . La suma de Minkowski de una bola cerrada y una bola abierta es una bola abierta. De manera más general, la suma de Minkowski de un subconjunto abierto con cualquier otro conjunto será un subconjunto abierto. ${\displaystyle \mathbb {K} ,}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {C} .}$ ${\displaystyle B_{r}:=\{s\in \mathbb {K} :|s|\leq r\}}$ ${\displaystyle r\in [0,\infty ]}$ ${\displaystyle 0}$ ${\displaystyle \mathbb {K} }$ ${\displaystyle r,s\in [0,\infty ],}$ ${\displaystyle B_{r}+B_{s}=B_{r+s}}$ ${\displaystyle cB_{r}=B_{|c|r}}$ ${\displaystyle c\in \mathbb {K} }$ ${\displaystyle |c|r}$ ${\displaystyle c\neq 0}$ ${\displaystyle r\neq \infty }$ ${\displaystyle r,s,}$ ${\displaystyle c}$ ${\displaystyle B_{r}}$ ${\displaystyle 0}$ ${\displaystyle 0}$

Si es la gráfica de y si y es el eje - entonces la suma de Minkowski de estos dos subconjuntos cerrados del plano es el conjunto abierto que consta de todo lo que no sea el eje -. Esto muestra que la suma de Minkowski de dos conjuntos cerrados no es necesariamente un conjunto cerrado. Sin embargo, la suma de Minkowski de dos subconjuntos cerrados será un subconjunto cerrado si al menos uno de estos conjuntos es también un subconjunto compacto . ${\displaystyle G=\{(x,1/x):0\neq x\in \mathbb {R} \}}$ ${\displaystyle f(x)={\frac {1}{x}}}$ ${\displaystyle Y=\{0\}\times \mathbb {R} }$ ${\displaystyle y}$ ${\displaystyle X=\mathbb {R} ^{2}}$ ${\displaystyle G+Y=\{(x,y)\in \mathbb {R} ^{2}:x\neq 0\}=\mathbb {R} ^{2}\setminus Y}$ ${\displaystyle y}$

Cascos convexos de sumas de Minkowski

La suma de Minkowski se comporta bien con respecto a la operación de tomar cascos convexos , como lo muestra la siguiente proposición:

Para todos los subconjuntos no vacíos y de un espacio vectorial real, la casco convexo de su suma de Minkowski es la suma de Minkowski de sus cascos convexos: ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$

${\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}$

Este resultado es válido de manera más general para cualquier colección finita de conjuntos no vacíos:

${\textstyle \operatorname {Conv} \left(\sum {S_{n}}\right)=\sum \operatorname {Conv} (S_{n}).}$

En terminología matemática, las operaciones de suma de Minkowski y de formación de cascos convexos son operaciones de conmutación . ^{[4] [5]}

Si es un conjunto convexo entonces también lo es; además ${\displaystyle S}$ ${\displaystyle \mu S+\lambda S}$

${\displaystyle \mu S+\lambda S=(\mu +\lambda )S}$

para cada . Por el contrario, si esta " propiedad distributiva " se cumple para todos los números reales no negativos, entonces el conjunto es convexo. ^[6] ${\displaystyle \mu ,\lambda \geq 0}$ ${\displaystyle \mu ,\lambda }$

Un ejemplo de un conjunto no convexo tal que ${\displaystyle A+A\neq 2A.}$

La figura de la derecha muestra un ejemplo de un conjunto no convexo para el cual ${\displaystyle A+A\subsetneq 2A.}$

Un ejemplo en dimensión es: Se puede calcular fácilmente eso , pero por lo tanto nuevamente ${\displaystyle 1}$ ${\displaystyle B=[1,2]\cup [4,5].}$ ${\displaystyle 2B=[2,4]\cup [8,10]}$ ${\displaystyle B+B=[2,4]\cup [5,7]\cup [8,10],}$ ${\displaystyle B+B\subsetneq 2B.}$

Las sumas de Minkowski actúan linealmente sobre el perímetro de cuerpos convexos bidimensionales: el perímetro de la suma es igual a la suma de los perímetros. Además, si es (el interior de) una curva de ancho constante , entonces la suma de Minkowski de y de su rotación es un disco. Estos dos hechos se pueden combinar para dar una breve demostración del teorema de Barbier sobre el perímetro de curvas de ancho constante. ^[7] ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle 180^{\circ }}$

Aplicaciones

La suma de Minkowski juega un papel central en la morfología matemática . Surge en el paradigma de pincelada de los gráficos por computadora 2D (con varios usos, en particular por Donald E. Knuth en Metafont ), y como la operación de barrido sólido de los gráficos por computadora 3D . También se ha demostrado que está estrechamente relacionado con la distancia del motor de la Tierra y, por extensión, con el transporte óptimo . ^[8]

Planificación de movimiento

Las sumas de Minkowski se utilizan en la planificación del movimiento de un objeto entre obstáculos. Se utilizan para el cálculo del espacio de configuración , que es el conjunto de todas las posiciones admisibles del objeto. En el modelo simple de movimiento de traslación de un objeto en el plano, donde la posición de un objeto puede especificarse únicamente por la posición de un punto fijo de este objeto, el espacio de configuración es la suma de Minkowski del conjunto de obstáculos y los obstáculos móviles. Objeto colocado en el origen y girado 180 grados.

Mecanizado de control numérico (NC)

En el mecanizado de control numérico , la programación de la herramienta NC aprovecha el hecho de que la suma de Minkowski de la pieza de corte con su trayectoria da la forma del corte en el material.

modelado de sólidos 3D

En OpenSCAD, las sumas de Minkowski se utilizan para delinear una forma con otra forma, creando una combinación de ambas formas.

Teoría de la agregación

Las sumas de Minkowski también se utilizan con frecuencia en la teoría de la agregación cuando los objetos individuales que se van a agregar se caracterizan mediante conjuntos. ^{[9] [10]}

Detección de colisiones

Las sumas de Minkowski, específicamente las diferencias de Minkowski, se utilizan a menudo junto con los algoritmos GJK para calcular la detección de colisiones para cascos convexos en motores de física .

Algoritmos para calcular sumas de Minkowski

Adición de Minkowski y cascos convexos. Los dieciséis puntos de color rojo oscuro (a la derecha) forman la suma de Minkowski de los cuatro conjuntos no convexos (a la izquierda), cada uno de los cuales consta de un par de puntos rojos. Sus cascos convexos (sombreados en rosa) contienen signos más (+): el signo más derecho es la suma de los signos más izquierdos.

caso plano

Dos polígonos convexos en el plano.

Para dos polígonos convexos P y Q en el plano con m y n vértices, su suma de Minkowski es un polígono convexo con como máximo m + n vértices y puede calcularse en el tiempo O( m + n ) mediante un procedimiento muy simple, que puede describirse informalmente de la siguiente manera. Supongamos que se dan los bordes de un polígono y la dirección, digamos, en sentido contrario a las agujas del reloj, a lo largo del límite del polígono. Entonces se ve fácilmente que estas aristas del polígono convexo están ordenadas por ángulo polar . Fusionemos las secuencias ordenadas de los bordes dirigidos de P y Q en una única secuencia ordenada S. Imagine que estos bordes son flechas sólidas que se pueden mover libremente manteniéndolas paralelas a su dirección original. Ensamble estas flechas en el orden de la secuencia S uniendo la cola de la siguiente flecha a la punta de la flecha anterior. Resulta que la cadena poligonal resultante será, de hecho, un polígono convexo que es la suma de Minkowski de P y Q.

Otro

Si un polígono es convexo y otro no, la complejidad de su suma de Minkowski es O( nm ). Si ambos son no convexos, su complejidad de suma de Minkowski es O(( mn ) ² ).

Suma esencial de Minkowski

También existe una noción de suma esencial de Minkowski + _e de dos subconjuntos del espacio euclidiano. La suma habitual de Minkowski se puede escribir como

${\displaystyle A+B=\left\{z\in \mathbb {R} ^{n}\,|\,A\cap (z-B)\neq \emptyset \right\}.}$

Por tanto, la suma esencial de Minkowski está definida por

${\displaystyle A+_{\mathrm {e} }B=\left\{z\in \mathbb {R} ^{n}\,|\,\mu \left[A\cap (z-B)\right]>0\right\},}$

donde μ denota la medida de Lebesgue n -dimensional . La razón del término "esencial" es la siguiente propiedad de las funciones indicadoras : mientras

${\displaystyle 1_{A\,+\,B}(z)=\sup _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

Puede observarse que

${\displaystyle 1_{A\,+_{\mathrm {e} }\,B}(z)=\mathop {\mathrm {ess\,sup} } _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

donde "ess sup" denota el supremo esencial .

Lp suma de Minkowski

Para K y L subconjuntos convexos compactos en , la suma de Minkowski puede describirse mediante la función de soporte de los conjuntos convexos: ${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle h_{K+L}=h_{K}+h_{L}.}$

Para p ≥ 1, Firey ^[11] definió la suma L ^p Minkowski K + _p L de conjuntos convexos compactos K y L al contener el origen como ${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle h_{K+_{p}L}^{p}=h_{K}^{p}+h_{L}^{p}.}$

Por la desigualdad de Minkowski , la función h _{K+ p L} es nuevamente homogénea y convexa positiva y, por tanto, la función de soporte de un conjunto convexo compacto. Esta definición es fundamental en la teoría de L ^p Brunn-Minkowski.

Ver también

• Suma de Blaschke  : politopo que combina dos politopos más pequeños
• Teorema de Brunn-Minkowski  - teorema en geometría Pages displaying wikidata descriptions as a fallback, una desigualdad en los volúmenes de las sumas de Minkowski
• Convolución  : integral que expresa la cantidad de superposición de una función a medida que se desplaza sobre otra.
• Dilatación  – Operación en morfología matemática
• Erosión  – Operación básica en morfología matemática
• Aritmética de intervalos  : método para delimitar los errores de cálculos numéricos
• Volumen mixto (también conocido como Quermassintegral o volumen intrínseco)
• Curva paralela
• Lema de Shapley-Folkman  : las sumas de conjuntos de vectores son casi convexas
• Suma  : conjunto de todas las sumas posibles de un elemento del conjunto A y un elemento del conjunto BPages displaying wikidata descriptions as a fallback
• Espacio vectorial topológico#Propiedades  – Espacio vectorial con noción de cercanía
• Zonotopo  : poliedro convexo proyectado desde un hipercuboPages displaying short descriptions of redirect targets

Notas

1. Hadwiger, Hugo (1950), "Minkowskische Suma y resta beliebiger Punktmengen und die Theoreme von Erhard Schmidt", Matemáticas. Z. , 53 (3): 210–218, doi :10.1007/BF01175656, S2CID  121604732 , consultado el 12 de enero de 2023
2. Li, Wei (otoño de 2011). Computación basada en GPU de sumas de Minkowski voxelizadas con aplicaciones (Doctor). UC Berkeley . págs. 13-14 . Consultado el 10 de enero de 2023 .
3. Lozano-Pérez, Tomás (febrero de 1983). "Planificación espacial: un enfoque espacial de configuración" (PDF) . Transacciones IEEE en computadoras . C-32 (2): 111. doi :10.1109/TC.1983.1676196. hdl :1721.1/5684. S2CID  18978404 . Consultado el 10 de enero de 2023 .
4. Teorema 3 (páginas 562–563): Krein, M .; Šmulian, V. (1940). "En conjuntos regularmente convexos en el espacio conjugado con un espacio de Banach". Anales de Matemáticas . Segunda Serie. 41 (3): 556–583. doi :10.2307/1968735. JSTOR  1968735. SEÑOR  0002009.
5. Para conocer la conmutatividad de la suma y convexificación de Minkowski , consulte el Teorema 1.1.2 (páginas 2-3) en Schneider; esta referencia analiza gran parte de la literatura sobre los cascos convexos de las sumas de Minkowski en su "Capítulo 3 Adición de Minkowski" (páginas 126-196): Schneider, Rolf (1993). Cuerpos convexos: la teoría de Brunn-Minkowski. Enciclopedia de matemáticas y sus aplicaciones. vol. 44. Cambridge: Prensa de la Universidad de Cambridge. págs. xiv+490. ISBN 978-0-521-35220-8. SEÑOR  1216521.
6. Capítulo 1: Schneider, Rolf (1993). Cuerpos convexos: la teoría de Brunn-Minkowski. Enciclopedia de matemáticas y sus aplicaciones. vol. 44. Cambridge: Prensa de la Universidad de Cambridge. págs. xiv+490. ISBN 978-0-521-35220-8. SEÑOR  1216521.
7. El teorema de Barbier (Java) en Cut-The-Knot .
8. Kline, Jeffery (2019). "Propiedades del problema del motor de tierra d-dimensional". Matemática Aplicada Discreta . 265 : 128-141. doi : 10.1016/j.dam.2019.02.042 . S2CID  127962240.
9. Zelenyuk, V (2015). "Agregación de eficiencia de escala". Revista europea de investigación operativa . 240 (1): 269–277. doi :10.1016/j.ejor.2014.06.038.
10. Mayer, A.; Zelenyuk, V. (2014). "Agregación de índices de productividad de Malmquist que permiten la reasignación de recursos". Revista europea de investigación operativa . 238 (3): 774–785. doi :10.1016/j.ejor.2014.04.003.
11. Firey, William J. (1962), " p -medias de cuerpos convexos", Math. Escanear. , 10 : 17–24, doi : 10.7146/math.scand.a-10510

Referencias

• Flecha, Kenneth J .; Hahn, Frank H. (1980). Análisis competitivo general . Libros de texto avanzados en economía. vol. 12 (reimpresión de (1971) San Francisco, CA: Holden-Day, Inc. Textos de economía matemática.  6  ed.). Amsterdam: Holanda Septentrional. ISBN 978-0-444-85497-1. SEÑOR  0439057.
• Gardner, Richard J. (2002), "La desigualdad de Brunn-Minkowski", Bull. América. Matemáticas. Soc. (NS) , 39 (3): 355–405 (electrónico), doi : 10.1090/S0273-0979-02-00941-2
• Verde, Jerry; Heller, Walter P. (1981). "1 Análisis matemático y convexidad con aplicaciones a la economía". En Flecha, Kenneth Joseph ; Intriligador, Michael D (eds.). Manual de economía matemática, volumen  I.. Manuales de economía. vol. 1. Ámsterdam: North-Holland Publishing Co. págs. 15–52. doi :10.1016/S1573-4382(81)01005-9. ISBN 978-0-444-86126-9. SEÑOR  0634800.
• Henry Mann (1976), Teoremas de la suma: los teoremas de la suma de la teoría de grupos y la teoría de números (reimpresión corregida de Wiley ed. de 1965), Huntington, Nueva York: Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5– a través de www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html
• Rockafellar, R. Tyrrell (1997). Análisis convexo . Hitos de Princeton en matemáticas (Reimpresión de la serie matemática de Princeton de 1979,  28  ed.). Princeton, Nueva Jersey: Princeton University Press. págs. xviii+451. ISBN 978-0-691-01586-6. SEÑOR  1451876.
• Nathanson, Melvyn B. (1996), Teoría de números aditivos: problemas inversos y geometría de sumas , GTM, vol. 165, Springer, Zbl  0859.11003.
• Vale, Eduardo; Sharir, Micha (2006), "Sumas de Minkowski de polígonos monótonos y simples generales", Geometría computacional y discreta , 35 (2): 223–240, doi : 10.1007/s00454-005-1206-y.
• Schneider, Rolf (1993), Cuerpos convexos: la teoría de Brunn-Minkowski , Cambridge: Cambridge University Press.
• Tao, Terence y Vu, Van (2006), Combinatoria aditiva , Cambridge University Press.
• Mayer, A.; Zelenyuk, V. (2014). "Agregación de índices de productividad de Malmquist que permiten la reasignación de recursos". Revista europea de investigación operativa . 238 (3): 774–785. doi :10.1016/j.ejor.2014.04.003.
• Zelenyuk, V (2015). "Agregación de eficiencia de escala". Revista europea de investigación operativa . 240 (1): 269–277. doi :10.1016/j.ejor.2014.06.038.

enlaces externos

• "Adición de Minkowski", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Howe, Roger (1979), Sobre la tendencia hacia la convexidad de la suma vectorial de conjuntos, artículos de debate de la Fundación Cowles, vol. 538, Fundación Cowles para la Investigación en Economía , Universidad de Yale
• Sumas de Minkowski, en la biblioteca de algoritmos de geometría computacional
• La suma de Minkowski de dos triángulos y la suma de Minkowski de un disco y un polígono de George Beck, The Wolfram Demonstrations Project .
• La adición de formas convexas de Minkowski por Alexander Bogomolny : un subprograma
• Wikilibros:Manual de usuario de OpenSCAD/Transformaciones#minkowski de Marius Kintel: Aplicación
• Aplicación de la adición de Minkowski a la robótica por Joan Gerard
• Demostración de la aditividad de Minkowski, la monotonicidad convexa y otras propiedades de la distancia de los Earth Movers