stringtranslate.com

Adición de Minkowski

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 en A a cada vector en B :

La diferencia de Minkowski (también sustracción 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. Esto se define como el complemento de la suma de Minkowski del complemento de A con la reflexión de B sobre el origen. [2]

Esta definición permite una relación simétrica entre la suma y la diferencia de Minkowski. Nótese que tomar alternativamente la suma y la diferencia con B no es necesariamente equivalente. La suma puede llenar espacios que la diferencia no puede reabrir, y la diferencia puede borrar pequeñas islas que la suma no puede recrear de la nada.

En el procesamiento de imágenes 2D , la suma y la 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] Esta no es equivalente a la definición anterior y no es una operación inversa de la suma. En cambio, reemplaza la suma vectorial de la suma de Minkowski con una resta vectorial . Si las dos formas convexas se intersecan, el conjunto resultante contendrá el origen.

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 ellos formado por 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 y su centro.

Para la adición de Minkowski, el conjunto cero , que contiene solo el vector cero , 0, es un elemento 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 cualquier otro subconjunto: para cada subconjunto S de un espacio vectorial, su suma con el conjunto vacío es 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 los números complejos Si es la bola cerrada de radio centrada en en entonces para cualquier y también se cumplirán para cualquier escalar tal que el producto esté definido (lo que sucede cuando o ). Si y son todos distintos de cero, entonces las mismas igualdades todavía se cumplirían si se hubieran 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 el gráfico 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 demuestra 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 .

Envolventes convexos de las sumas de Minkowski

La adición de Minkowski se comporta bien con respecto a la operación de tomar envolturas convexas , como lo demuestra la siguiente proposición:

Para todos los subconjuntos no vacíos y de un espacio vectorial real, la envoltura convexa de su suma de Minkowski es la suma de Minkowski de sus envolturas convexas:

Este resultado se aplica de forma más general a cualquier colección finita de conjuntos no vacíos:

En terminología matemática, las operaciones de suma de Minkowski y de formación de envolturas convexas son operaciones conmutativas . [4] [5]

Si es un conjunto convexo entonces también es un conjunto convexo; ademá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]

Un ejemplo de un conjunto no convexo tal que

La figura de la derecha muestra un ejemplo de un conjunto no convexo para el cual

Un ejemplo de dimensión es: Se puede calcular fácilmente que pero por lo tanto nuevamente

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 prueba breve del teorema de Barbier sobre el perímetro de curvas de ancho constante. [7]

Aplicaciones

La adición de Minkowski desempeña un papel central en la morfología matemática . Surge en el paradigma de pincelada y trazo de los gráficos por ordenador en 2D (con diversos usos, en particular por parte de Donald E. Knuth en Metafont ) y como la operación de barrido sólido de los gráficos por ordenador en 3D . También se ha demostrado que está estrechamente relacionada con la distancia de la excavadora y, por extensión, con el transporte óptimo . [8]

Planificación del 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 forma única mediante 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 el objeto móvil colocado en el origen y rotado 180 grados.

Mecanizado por 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 en 3D

En OpenSCAD, las sumas de Minkowski se utilizan para delinear una forma con otra forma, creando una composició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 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

Suma de Minkowski de cuatro segmentos de línea. El panel izquierdo muestra cuatro conjuntos, que se muestran en una matriz de dos por dos. Cada uno de los conjuntos contiene exactamente dos puntos, que se muestran en rojo. En cada conjunto, los dos puntos están unidos por un segmento de línea rosa, que es la envoltura convexa del conjunto original. Cada conjunto tiene exactamente un punto que se indica con un símbolo más. En la fila superior de la matriz de dos por dos, el símbolo más se encuentra en el interior del segmento de línea; en la fila inferior, el símbolo más coincide con uno de los puntos rojos. Esto completa la descripción del panel izquierdo del diagrama. El panel derecho muestra la suma de Minkowski de los conjuntos, que es la unión de las sumas que tienen exactamente un punto de cada conjunto de sumandos; para los conjuntos mostrados, las dieciséis sumas son puntos distintos, que se muestran en rojo: Los puntos de suma rojos de la derecha son las sumas de los puntos de sumando rojos de la izquierda. La envoltura convexa de los dieciséis puntos rojos está sombreada en rosa. En el interior rosa del conjunto sumando de la derecha se encuentra exactamente un símbolo más, que es la suma (única) de los símbolos más del lado derecho. El símbolo más de la derecha es, de hecho, la suma de los cuatro símbolos más de los conjuntos de la izquierda, exactamente dos puntos de los conjuntos sumandos no convexos originales y dos puntos de las envolturas convexas de los conjuntos sumandos restantes.
Adición de Minkowski y envolturas convexas. 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 envolturas convexas (sombreadas en rosa) contienen signos más (+): el signo más de la derecha es la suma de los signos más de la izquierda.

Caso planar

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 a lo sumo m + n vértices y puede calcularse en tiempo O( m + n ) mediante un procedimiento muy simple, que puede describirse informalmente como sigue. Supongamos 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 . Fusionemos las secuencias ordenadas de los bordes dirigidos de P y Q en una única secuencia ordenada S . Imaginemos que estos bordes son flechas sólidas que se pueden mover libremente mientras se mantienen paralelas a su dirección original. Ensamblemos 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, la complejidad de su suma de Minkowski es O(( mn ) 2 ).

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

Por tanto, 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 lo esencial supremo .

L pSuma de Minkowski

Para los 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 [11] definió la suma de Minkowski L p K + p L de los conjuntos convexos compactos K y L que contienen el origen como

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

Véase también

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). Cálculo basado en GPU de sumas de Minkowski voxelizadas con aplicaciones (doctorado). 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) . IEEE Transactions on Computers . 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). "Sobre conjuntos regularmente convexos en el espacio conjugado a un espacio de Banach". Anales de Matemáticas . Segunda serie. 41 (3): 556–583. doi :10.2307/1968735. JSTOR  1968735. MR  0002009.
  5. ^ Para la conmutatividad de la suma y convexificación de Minkowski , véase el teorema 1.1.2 (páginas 2-3) en Schneider; esta referencia analiza gran parte de la literatura sobre las envolturas convexas de los conjuntos suma de Minkowski en su "Capítulo 3 Suma 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: Cambridge University Press. pp. 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: Cambridge University Press. pp. 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 movimiento de tierra de dimensión d". Matemáticas Aplicadas Discretas . 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. Scand. , 10 : 17–24, doi : 10.7146/math.scand.a-10510

Referencias

Enlaces externos