Hispanopedia Wiki
Articulo de referencia

Conjunto Delone

Los puntos rojos forman parte de una red ε para el plano euclidiano , donde ε es el radio de los discos amarillos grandes. Los discos azules, de la mitad del radio, son disjunto...

Hispanopedia WikiContenido en espanolLectura gratuita
Los puntos rojos forman parte de una red ε para el plano euclidiano , donde ε es el radio de los discos amarillos grandes. Los discos azules, de la mitad del radio, son disjuntos , y los discos amarillos juntos cubren todo el plano, satisfaciendo así los dos requisitos de definición de una red ε .

En la teoría matemática de espacios métricos , las ε- redes , los ε- empaquetamientos , los ε- recubrimientos , los conjuntos uniformemente discretos , los conjuntos relativamente densos y los conjuntos de Delone (llamados así en honor a Boris Delone ) son varias definiciones estrechamente relacionadas de conjuntos de puntos bien espaciados , y el radio de empaquetamiento y el radio de recubrimiento de estos conjuntos miden qué tan bien espaciados están. Estos conjuntos tienen aplicaciones en la teoría de la codificación , los algoritmos de aproximación y la teoría de los cuasicristales .

Definiciones

Si ( M , d ) es un espacio métrico y X es un subconjunto de M , entonces el radio de empaquetamiento , r , de X es la mitad del ínfimo de las distancias entre elementos distintos de X . Las bolas abiertas de radio r centradas en los puntos de X serán todas disjuntas entre sí. El radio de recubrimiento , R , de X es la distancia más pequeña tal que cada punto de M está a una distancia R de al menos un punto en X ; es decir, R es el radio más pequeño tal que las bolas cerradas de ese radio centradas en los puntos de X tienen como unión todo M .

Un ε -empaquetamiento es un conjunto X de radio de empaquetamiento r ≥ ε /2 (equivalentemente, distancia mínima ≥ ε ), un ε -recubrimiento es un conjunto X de radio de recubrimiento R ≤ ε , y una ε -red es un conjunto que es a la vez un ε- empaquetamiento y un ε -recubrimiento ( ε /2 ≤ r ≤ R ≤ ε ).

Un conjunto es uniformemente discreto si tiene un radio de empaquetamiento distinto de cero ( 0 < r ), y relativamente denso si tiene un radio de cobertura finito ( R < ∞ ).

Un conjunto de Delone es un conjunto que es uniformemente discreto y relativamente denso ( 0 < r ≤ R < ∞ ). Por lo tanto, toda ε -red es de Delone, pero no a la inversa. [ 1 ] [ 2 ]

Construcción de redes ε

Como la más restrictiva de las definiciones anteriores, las ε -redes son al menos tan difíciles de construir como los ε- empaquetamientos, los ε- recubrimientos y los conjuntos de Delone. Sin embargo, siempre que los puntos de M tengan un buen ordenamiento , la inducción transfinita muestra que es posible construir una ε -red N , incluyendo en N cada punto para el cual el ínfimo de distancias al conjunto de puntos anteriores en el ordenamiento sea al menos ε . Para conjuntos finitos de puntos en un espacio euclidiano de dimensión acotada, cada punto puede ser probado en tiempo constante mapeándolo a una cuadrícula de celdas de diámetro ε , y usando una tabla hash para probar qué celdas cercanas ya contienen puntos de N ; por lo tanto, en este caso, una ε -red puede construirse en tiempo lineal . [ 3 ] [ 4 ] 

Para espacios métricos finitos o compactos más generales, se puede utilizar un algoritmo alternativo de Teo González basado en el recorrido del más lejano primero para construir una red ε finita . Este algoritmo inicializa la red N vacía y luego agrega repetidamente a N el punto más lejano de M desde N , resolviendo los empates arbitrariamente y deteniéndose cuando todos los puntos de M están dentro de una distancia ε de N. [ 5 ] En espacios de dimensión de duplicación acotada , el algoritmo de González se puede implementar en tiempo O( n log n ) para conjuntos de puntos con una razón polinómica entre sus distancias más lejanas y más cercanas, y se aproxima en el mismo límite de tiempo para conjuntos de puntos arbitrarios. [ 6 ]   

Aplicaciones

Teoría de la codificación

En la teoría de los códigos correctores de errores , el espacio métrico que contiene un código de bloque C consta de cadenas de longitud fija, digamos n , tomadas sobre un alfabeto de tamaño q (que puede pensarse como vectores ), con la métrica de Hamming . Este espacio se denota por ⁠Aqnorte.{\displaystyle {\mathcal {A}}_{q}^{n}.}El radio de cobertura y el radio de empaquetamiento de este espacio métrico están relacionados con la capacidad del código para corregir errores. Un ejemplo lo proporciona el juego de conmutación de Berlekamp .

Algoritmos de aproximación

Har-Peled y Raichel (2013) describen un paradigma algorítmico que denominan "red y poda" para diseñar algoritmos de aproximación para ciertos tipos de problemas de optimización geométrica definidos en conjuntos de puntos en espacios euclidianos . Un algoritmo de este tipo funciona realizando los siguientes pasos:

  1. Elija un punto aleatorio p del conjunto de puntos, encuentre su vecino más cercano q y establezca ε como la distancia entre p y q .
  2. Compruebe si ε es (aproximadamente) mayor o menor que el valor de la solución óptima (utilizando una técnica específica para el problema de optimización que se está resolviendo).
    • Si es mayor, elimine de la entrada los puntos cuyo vecino más cercano esté más lejos que ε.
    • Si es más pequeño, construya una ε -red N y elimine de la entrada los puntos que no están en N.

En ambos casos, el número esperado de puntos restantes disminuye en un factor constante, por lo que el tiempo está dominado por la etapa de prueba. Como demuestran, este paradigma puede utilizarse para construir algoritmos de aproximación rápidos para la agrupación de k centros , la búsqueda de un par de puntos con distancia mediana y varios problemas relacionados.

Un sistema jerárquico de redes, llamado árbol de redes , puede utilizarse en espacios de dimensión de duplicación acotada para construir descomposiciones de pares bien separadas , expansores geométricos y vecinos más cercanos aproximados . [ 6 ] [ 7 ]

Cristalografía

Para puntos en el espacio euclidiano , un conjunto X es un conjunto de Meyer si es relativamente denso y su conjunto diferencia X − X es uniformemente discreto. De forma equivalente, X es un conjunto de Meyer si tanto X como X − X son conjuntos de Delone. Los conjuntos de Meyer reciben su nombre de Yves Meyer , quien los introdujo (con una definición diferente pero equivalente basada en el análisis armónico ) como un modelo matemático para cuasicristales . Incluyen los conjuntos de puntos de retículos , los teselados de Penrose y las sumas de Minkowski de estos conjuntos con conjuntos finitos. [ 8 ]

Las celdas de Voronoi de los conjuntos de Delone simétricos forman poliedros que llenan el espacio llamados plesioedros . [ 9 ]

Referencias

  1. ↑ Clarkson, Kenneth L. (2006), "Building triangulations using ε- nets", STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing , Nueva York: ACM, pp. 326– 335, doi : 10.1145/1132516.1132564 , ISBN  1595931341, MR 2277158 , S2CID 14132888  
  2. ↑ Algunas fuentes utilizan « ε -red» para lo que aquí se denomina « ε- recubrimiento»; véase, por ejemplo , Sutherland, WA (1975), Introduction to metric and topological spaces , Oxford University Press, p. 110, ISBN  0-19-853161-3, Zbl 0304.54002 
  3. ↑ Har-Peled, S. (2004), "Agrupamiento del movimiento", Geometría discreta y computacional , 31 (4): 545– 565, doi : 10.1007/s00454-004-2822-7 , MR 2053498 
  4. ↑ Har-Peled, S.; Raichel, B. (2013), "Net and prune: A linear time algorithm for Euclidean distance problems", STOC'13: Proceedings of the 45th Annual ACM Symposium on Theory of Computing , pp. 605– 614, arXiv : 1409.7425 
  5. ↑ González, TF (1985), "Agrupamiento para minimizar la distancia máxima entre clústeres", Theoretical Computer Science , 38 ( 2–3 ): 293–306 , doi : 10.1016/0304-3975(85)90224-5 , MR 0807927 
  6. 1 2 Har-Peled, S.; Mendel, M. (2006), "Construcción rápida de redes en métricas de baja dimensión y sus aplicaciones", SIAM Journal on Computing , 35 (5): 1148– 1184, arXiv : cs/0409057 , doi : 10.1137/S0097539704446281 , MR 2217141 , S2CID 37346335  
  7. ↑ Krauthgamer, Robert; Lee, James R. (2004), "Navegando redes: algoritmos simples para la búsqueda de proximidad", Actas del 15.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA '04) , Filadelfia, PA, EE. UU.: Society for Industrial and Applied Mathematics, págs. 798–807 , ISBN  0-89871-558-X
  8. ↑ Moody, Robert V. (1997), "Conjuntos de Meyer y sus duales", The Mathematics of Long-Range Aperiodic Order (Waterloo, ON, 1995) , NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 489, Dordrecht: Kluwer Academic Publishers, pp. 403–441 , MR 1460032 , archivado del original el 3 de marzo de 2016 , recuperado el 10 de julio de 2013.   
  9. ↑ Grünbaum, Branko ; Shephard, GC (1980), "Teselaciones con teselas congruentes", Boletín de la Sociedad Matemática Americana , Nueva Serie, 3 (3): 951– 973, doi : 10.1090/S0273-0979-1980-14827-2 , MR 0585178 
  • Conjunto Delone – Enciclopedia de teselaciones