stringtranslate.com

Conjunto Delone

Los puntos rojos forman parte de una ε -red para el plano euclidiano , donde ε es el radio de los grandes discos amarillos. Los discos azules de la mitad del radio están disjuntos y los discos amarillos juntos cubren todo el plano, satisfaciendo los dos requisitos de definición de una ε -red.

En la teoría matemática de los espacios métricos , las ε -redes , los ε -empaquetamientos , los ε -cubrimientos , los conjuntos uniformemente discretos , los conjuntos relativamente densos y los conjuntos de Delone (nombrados 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 codificación , los algoritmos de aproximación y la teoría de 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 de la distancia más pequeña entre miembros distintos de X . Las bolas abiertas de radio r centradas en los puntos de X estarán todas disjuntas entre sí. El radio de empaquetamiento , R , de X es la distancia más pequeña tal que cada punto de M está dentro de la 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 todo M como su unión.

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

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 Delone es un conjunto que es uniformemente discreto y relativamente denso ( 0 < rR < ∞ ). Por lo tanto, cada ε -net es Delone, pero no viceversa. [1] [2]

Construcción demi-redes

Como la más restrictiva de las definiciones anteriores, las ε -redes son al menos tan difíciles de construir como los ε -empaquetamientos, ε -cubrimientos y 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 probarse 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 más lejano primero para construir una ε -red finita. Este algoritmo inicializa la red N para que esté vacía, y luego agrega repetidamente a N el punto más alejado en M desde N , rompiendo los empates arbitrariamente y deteniéndose cuando todos los puntos de  M están dentro de la 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 aproximarse 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 códigos correctores de errores , el espacio métrico que contiene un código de bloque C consiste en cadenas de una longitud fija, digamos n , tomadas sobre un alfabeto de tamaño q (pueden considerarse como vectores ), con la métrica de Hamming . Este espacio se denota por ⁠ ⁠ 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 "net and prune" para diseñar algoritmos de aproximación para ciertos tipos de problemas de optimización geométrica definidos sobre 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. Pruebe 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 particular 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 menor, 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 el paso de prueba. Como muestran, este paradigma se puede utilizar 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.

Se puede utilizar un sistema jerárquico de redes, llamado árbol de redes , en espacios de dimensión de duplicación acotada para construir descomposiciones de pares bien separados , llaves geométricas y vecinos más cercanos aproximados . [6] [7]

Cristalografía

Para los puntos en el espacio euclidiano , un conjunto X es un conjunto de Meyer si es relativamente denso y su conjunto de diferencias XX es uniformemente discreto. De manera equivalente, X es un conjunto de Meyer si tanto X como XX 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 los cuasicristales . Incluyen los conjuntos puntuales de las redes , los teselados de Penrose y las sumas de Minkowski de estos conjuntos con conjuntos finitos. [8]

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

Referencias

  1. ^ Clarkson, Kenneth L. (2006), "Construcción de triangulaciones utilizando ε -nets", STOC'06: Actas del 38.º Simposio Anual de la ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 326-335, doi :10.1145/1132516.1132564, ISBN 1595931341, MR  2277158, S2CID  14132888.
  2. ^ Algunas fuentes utilizan " ε -net" para lo que aquí se llama una " ε -cobertura"; véase, por ejemplo, Sutherland, WA (1975), Introducción a los espacios métricos y topológicos , Oxford University Press, pág. 110, ISBN 0-19-853161-3, Zbl0304.54002 ​.
  3. ^ Har-Peled, S. (2004), "Movimiento de agrupamiento", 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: Un algoritmo de tiempo lineal para problemas de distancia euclidiana", STOC'13: Actas del 45.º Simposio anual de la ACM sobre teoría de la computación , págs. 605-614, arXiv : 1409.7425.
  5. ^ Gonzalez, 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. ^ ab 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 por redes: algoritmos simples para búsqueda de proximidad", Actas del 15.º Simposio anual ACM-SIAM sobre algoritmos discretos (SODA '04), Filadelfia, Pensilvania, 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 desde el original el 2016-03-03 , consultado el 2013-07-10.
  9. ^ Grünbaum, Branko ; Shephard, GC (1980), "Teselas con teselas congruentes", Boletín de la American Mathematical Society , Nueva serie, 3 (3): 951–973, doi : 10.1090/S0273-0979-1980-14827-2 , MR  0585178.

Enlaces externos