En geometría , la suma de Minkowski (también conocida como dilatación ) de dos conjuntos de vectores de posición A y B en el espacio euclidiano se forma sumando cada vector en A a cada vector en B , es decir, el conjunto
De manera análoga, la diferencia de Minkowski (o diferencia geométrica) [1] se define utilizando la operación de complemento como
En general . Por ejemplo, en un caso unidimensional y la diferencia de Minkowski , mientras que
En un caso bidimensional, la diferencia de Minkowski está estrechamente relacionada con la erosión (morfología) en el procesamiento de imágenes .
El concepto lleva el nombre de Hermann Minkowski .
Ejemplo
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
y
entonces su suma de Minkowski es
que comprende los vértices de un hexágono.
Para la adición de Minkowski, el conjunto de cero ,que contiene solo el vector cero , 0, es un elemento de identidad : para cada subconjunto S de un espacio vectorial,
El conjunto vacío es importante en la adición de Minkowski, porque el conjunto vacío aniquila a todos los demás subconjuntos: para cada subconjunto S de un espacio vectorial, su suma con el conjunto vacío está vacía:
Para otro ejemplo, considere las sumas de Minkowski de bolas abiertas o cerradas en el campo que son los números reales o números complejos Si es la bola cerrada de radio centrado en en entonces para cualquier y también se mantendrá para cualquier escalar tal que el producto está definido (lo que sucede cuando o ). Si y son todos distintos de cero, entonces se mantendrían las mismas igualdades si 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.
Si es la gráfica de y si y es el -eje en entonces la suma de Minkowski de estos dos subconjuntos cerrados del plano es el conjunto abierto que consiste en 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 también es un subconjunto compacto .
Cascos convexos de sumas de Minkowski
La adición 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, el casco convexo de su suma de Minkowski es la suma de Minkowski de sus cascos convexos:
Este resultado es válido de manera más general para cualquier colección finita de conjuntos no vacíos:
En terminología matemática, las operaciones de suma de Minkowski y de formar cascos convexos son operaciones de conmutación . [2] [3]
Si es un conjunto convexo entonces también es un conjunto convexo; además
para cada . Por el contrario, si esta " propiedad distributiva " es válida para todos los números reales no negativos,, entonces el conjunto es convexo. [4]
La figura de la derecha muestra un ejemplo de un conjunto no convexo para el que
Un ejemplo en la dimensión es: Se puede calcular fácilmente que pero por lo tanto de nuevo
Las sumas de Minkowski actúan linealmente sobre el perímetro de los cuerpos convexos bidimensionales: el perímetro de la suma es igual a la suma de los perímetros. Además, sies (el interior de) una curva de ancho constante , entonces la suma de Minkowski de y de su la rotación es un disco. Estos dos hechos se pueden combinar para dar una prueba breve del teorema de Barbier en el perímetro de curvas de ancho constante. [5]
Aplicaciones
La adición de Minkowski juega un papel central en la morfología matemática . Surge en el paradigma del pincel y trazo de los gráficos por computadora en 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 en 3D . También se ha demostrado que está estrechamente relacionado con la distancia del movimiento de la Tierra y, por extensión, un transporte óptimo . [6]
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 de manera única por la posición de un punto fijo de este objeto, el espacio de configuración son la suma de Minkowski del conjunto de obstáculos y el elemento móvil. 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 Minkowski se utilizan sumas para delinear una forma con otra forma creando un compuesto 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 a través de conjuntos. [7] [8]
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
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 un máximo de 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. Suponga que se dan los bordes de un polígono y la dirección, digamos, en sentido antihorario, a lo largo del límite del polígono. Entonces se ve fácilmente que estos bordes del polígono convexo están ordenados por ángulo polar . Vamos a fusionar las secuencias ordenadas de los bordes dirigidos de P y Q en una sola secuencia ordenada S . Imagine que estos bordes son flechas sólidas que se pueden mover libremente mientras se mantienen 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 resultante línea poligonal 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) 2 ).
Suma esencial de Minkowski
También existe una noción de la suma esencial de Minkowski + e de dos subconjuntos del espacio euclidiano. La suma habitual de Minkowski se puede escribir como
Así, la suma esencial de Minkowski se define por
donde μ denota la medida de Lebesgue n- dimensional . La razón del término "esencial" es la siguiente propiedad de las funciones indicadoras : mientras
Se puede ver que
donde "ess sup" denota el supremo esencial .
L p suma de Minkowski
Para subconjuntos convexos compactos K y L en, la suma de Minkowski se puede describir mediante la función de soporte de los conjuntos convexos:
Para p ≥ 1 , Firey [9] definió la suma de L p Minkowski K + p L de los conjuntos convexos compactos K y L en que contiene el origen como
Por la desigualdad de Minkowski , la función h K + p L es de nuevo positiva homogénea y convexa 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
- Teorema de Brunn-Minkowski , una desigualdad en los volúmenes de las sumas de Minkowksi
- Circunvolución
- Dilatación
- Erosión
- Aritmética de intervalos
- Volumen mixto (también conocido como Quermassintegral o volumen intrínseco )
- Curva paralela
- Lema de Shapley-Folkman
- Espacio vectorial topológico # Propiedades
- Zonotopo
Notas
- ^ Hadwiger, Hugo (1950), "Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt", Matemáticas. Z. , 53 (3): 210–218, doi : 10.1007 / BF01175656
- ^ Teorema 3 (páginas 562–563): Kerin, M .; Šmulian, V. (1940). "En conjuntos regularmente convexos en el espacio conjugado a un espacio de Banach". Annals of Mathematics . Segunda Serie. 41 . págs. 556–583. doi : 10.2307 / 1968735 . JSTOR 1968735 . Señor 0002009 .
- ↑ Para la conmutatividad de la suma y la 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 los conjuntos de Minkowskien 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 las matemáticas y sus aplicaciones. 44 . Cambridge: Cambridge University Press. págs. xiv + 490. ISBN 978-0-521-35220-8. Señor 1216521 .
- ^ Capítulo 1: Schneider, Rolf (1993). Cuerpos convexos: la teoría de Brunn-Minkowski . Enciclopedia de las matemáticas y sus aplicaciones. 44 . Cambridge: Cambridge University Press. págs. xiv + 490. ISBN 978-0-521-35220-8. Señor 1216521 .
- ^ El teorema de Barbier (Java) al cortar el nudo .
- ^ Kline, Jeffery (2019). "Propiedades del problema del movimiento de tierra d-dimensional". Matemáticas aplicadas discretas . 265 : 128-141. doi : 10.1016 / j.dam.2019.02.042 .
- ^ 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 .
- ^ 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 .
- ^ Firey, William J. (1962), " p -medios de cuerpos convexos", Math. Scand. , 10 : 17-24, doi : 10.7146 / math.scand.a-10510
Referencias
- Arrow, Kenneth J .; Hahn, Frank H. (1980). Análisis competitivo general . Libros de texto avanzados en economía. 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. Amer. Matemáticas. Soc. (NS) , 39 (3): 355–405 (electrónico), doi : 10.1090 / S0273-0979-02-00941-2
- Green, Jerry; Heller, Walter P. (1981). "1 Análisis matemático y convexidad con aplicaciones a la economía". En Arrow, Kenneth Joseph ; Intriligador, Michael D (eds.). Manual de economía matemática, Volumen I. Manuales de economía. 1 . Amsterdam: 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 1965 Wiley ed.), Huntington, Nueva York: Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5- a través de http://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 conjuntos , GTM, 165 , Springer, Zbl 0859.11003.
- Está bien, Eduard; Sharir, Micha (2006), "Minkowski Sums of Monotone and General Simple Polygons", Geometría discreta y computacional , 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 & 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 , documentos de discusión de la Fundación Cowles, 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 por George Beck, The Wolfram Demonstrations Project .
- La adición de Minkowski de formas convexas por Alexander Bogomolny : un applet
- Wikilibros: Manual de usuario de OpenSCAD / Transformaciones # minkowski por Marius Kintel: Aplicación
- Aplicación de Minkowski Addition a la robótica por Joan Gerard