En la teoría matemática de los espacios métricos , ε -nets , ε -packings , ε -coverings , conjuntos uniformemente discretos , conjuntos relativamente densos y conjuntos 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 cobertura de estos conjuntos miden qué tan bien espaciados están. Estos conjuntos tienen aplicaciones en teoría de codificación , algoritmos de aproximación y teoría de cuasicristales .
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 distintos miembros de X. Las bolas abiertas de radio r centradas en los puntos de X estarán todas separadas entre sí. El radio de cobertura , 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 tengan todo M como unión.
Un empaquetamiento ε es un conjunto X de radio de empaquetamiento r ≥ ε/2(de manera equivalente, distancia mínima ≥ ε ), una cobertura ε es un conjunto X de radio de cobertura R ≤ ε , y una red ε es un conjunto que es a la vez un embalaje ε y una cobertura ε ( ε/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 Delone es un conjunto que es uniformemente discreto y relativamente denso ( 0 < r ≤ R < ∞ ). Por tanto, cada ε -net es Delone, pero no al revés. [1] [2]
Como la más restrictiva de las definiciones anteriores, ε -nets son al menos tan difíciles de construir como ε -packings, ε -coverings y conjuntos Delone. Sin embargo, siempre que los puntos de M tienen un buen ordenamiento , la inducción transfinita muestra que es posible construir un ε -net N , incluyendo en N cada punto para el cual el mínimo de distancias al conjunto de puntos anteriores en el ordenamiento es al menos ε . Para conjuntos finitos de puntos en un espacio euclidiano de dimensión limitada, cada punto puede probarse en tiempo constante mapeándolo en 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, se puede construir una red ε 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 primer recorrido más lejano 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 de N , rompiendo los lazos 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 relación polinómica entre sus distancias más lejanas y más cercanas, y aproximarse en el mismo tiempo para conjuntos de puntos arbitrarios. [6]
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 consta de 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 cambio de Berlekamp .
Har-Peled & Raichel (2013) describen un paradigma algorítmico al que llaman "net and pode" 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:
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ápida para agrupaciones de centros k , encontrar un par de puntos con una distancia mediana y varios problemas relacionados.
Se puede utilizar un sistema jerárquico de redes, llamado árbol de red , 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]
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 conjuntos Delone. Los conjuntos de 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]
