En la teoría matemática de espacios métricos , varepsilon redes , varepsilon envases , varepsilon revestimientos , uniformemente conjuntos discretos , conjuntos relativamente densos , y los conjuntos Delone (el nombre de Boris Delone ) varias definiciones estrechamente relacionadas de conjuntos bien-espaciados de puntos, y el radio de embalaje y radio que cubre de estos conjuntos miden lo bien espaciados que son. 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 embalaje de X es la mitad de la infimum de distancias entre los miembros distintos de X . Si el radio de empaquetadura es r , entonces las bolas abiertas de radio r centradas en los puntos de X estarán todas disjuntas entre sí, y cada bola abierta centrada en uno de los puntos de X con radio 2 r estará disjunta del resto de X . El radio de cobertura de X es el mínimo de los números r tal que cada punto de M está dentro de la distancia r de al menos un punto en X ; es decir, 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 unión. Un ε -cajones es un conjunto X de embalaje radio ≥ ε / 2 (equivalentemente, distancia mínima ≥ ε), un ε-recubrimiento es un conjunto X de cubrir radio ≤ ε , y un ε-net es un conjunto que es a la vez una Embalaje ε y una cubierta ε . Un conjunto es uniformemente discreto si tiene un radio de empaquetamiento distinto de cero y relativamente denso si tiene un radio de cobertura finito. Un conjunto de Delone es un conjunto uniformemente discreto y relativamente denso; por tanto, cada ε -net es Delone, pero no al revés. [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 las empaquetaduras ε, las cubiertas ε y los conjuntos Delone. Sin embargo, siempre que los puntos de M tienen un buen orden , la inducción transfinita muestra que es posible construir un ε-net N , al incluir en N todos los puntos para los cuales el mínimo de distancias al conjunto de puntos anteriores en el orden es 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 tanto, en este caso, se puede construir una red ε en tiempo lineal . [3] [4]
Para espacios métricos finitos o compactos más generales, se puede usar un algoritmo alternativo de Teo González basado en el primer recorrido más lejano para construir una red ε finita. Este algoritmo se inicializa la red N a estar vacío, y después se añade varias veces para N el punto más lejano de M de N , rompiendo los lazos de forma arbitraria y deteniéndose cuando todos los puntos de M están a 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 relación polinomial entre sus distancias más lejanas y más cercanas, y aproximado 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 de corrección 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 (puede considerarse como vectores ), con la métrica de Hamming . Este espacio se denota por. El radio de cobertura y el radio de empaque de este espacio métrico están relacionados con la capacidad del código para corregir errores.
Algoritmos de aproximación
Har-Peled y Raichel (2013) describen un paradigma algorítmico al 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:
- Elegir un punto aleatorio p del conjunto de puntos, encuentra su vecino más cercano q , y el conjunto ε a la distancia entre p y q .
- 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, construir un-ε red N , y retirar de la entrada de 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 paso de prueba domina el tiempo. Como muestran, este paradigma se puede utilizar para construir algoritmos de aproximación rápida para la agrupación de centros k , encontrar un par de puntos con distancia media y varios problemas relacionados.
Se puede usar un sistema jerárquico de redes, llamado árbol de redes, en espacios de dimensión duplicada acotada para construir descomposiciones de pares bien separados , llaves geométricas 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 de diferencias X - X es uniformemente discreto. De manera equivalente, X es un conjunto de Meyer si tanto X como X - X son Delone. Los conjuntos Meyer llevan el nombre de Yves Meyer , quien los introdujo (con una definición diferente pero equivalente basada en el análisis armónico ) como modelo matemático para cuasicristales . Incluyen los conjuntos de puntos de celosías , los mosaicos 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]
Ver también
Referencias
- ^ Clarkson, Kenneth L. (2006), "Construyendo triangulaciones usando ε -nets", STOC'06: Actas del 38º Simposio Anual de ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 326–335, doi : 10.1145 / 1132516.1132564 , ISBN 1595931341, MR 2277158.
- ^ Algunas fuentes usan " ε -net" para lo que aquí se denomina " ε -covering"; ver, por ejemplo Sutherland, WA (1975), Introducción a los espacios métricos y topológicos , Oxford University Press, p. 110, ISBN 0-19-853161-3, Zbl 0304.54002.
- ^ Har-Peled, S. (2004), "Clustering motion", Geometría discreta y computacional , 31 (4): 545–565, doi : 10.1007 / s00454-004-2822-7 , MR 2053498.
- ^ Har-Peled, S .; Raichel, B. (2013), "Red y poda: un algoritmo de tiempo lineal para problemas de distancia euclidiana", STOC'13: Actas del 45º Simposio Anual de ACM sobre Teoría de la Computación , págs. 605–614, arXiv : 1409.7425.
- ^ González, TF (1985), "Agrupamiento para minimizar la distancia máxima entre grupos", Ciencias de la computación teóricas , 38 (2-3): 293-306, doi : 10.1016 / 0304-3975 (85) 90224-5 , MR 0807927.
- ^ a b 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 , Señor 2217141.
- ^ Krauthgamer, Robert; Lee, James R. (2004), "Navegación 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.: Sociedad de Matemáticas Industriales y Aplicadas , págs. 798–807, ISBN 0-89871-558-X.
- ^ Moody, Robert V. (1997), "Meyer sets and their duals", The Mathematics of Long-Range Aperiodic Order (Waterloo, ON, 1995) , NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, 489 , Dordrecht: Kluwer Editores académicos, págs. 403–441, MR 1460032.
- ^ Grünbaum, Branko ; Shephard, GC (1980), "Tilings with congruent tiles", Bulletin of the American Mathematical Society , New Series, 3 (3): 951–973, doi : 10.1090 / S0273-0979-1980-14827-2 , MR 0585178.
enlaces externos
- Delone set - Enciclopedia de Tilings