Conjunto de Delaunay

En la teoría matemática de espacios métricos, ε-redes, ε-empaquetados, ε-coberturas, conjuntos uniformemente discretos, conjuntos relativamente densos, y conjuntos de Delaunay (nombrados así en memoria del matemático ruso Borís Delaunay; también son denominados conjuntos de Delone) son muchas veces definiciones estrechamente relacionadas de conjuntos de puntos bien-ordenados, y la relación entre el radio de empaquetado y el radio de recubrimiento mide en qué grado están bien-ordenados. Estos conjuntos tienen aplicaciones en teoría de códigos, en algoritmos de aproximación, y en la teoría de cuasicristales.

Los puntos rojos forman parte de una ε-red en el plano Euclidiano, donde ε es el radio de los discos amarillos grandes. Los discos azules (con la mitad de la radio que los amarillos) son disjuntos, y el conjunto de todos los discos amarillos cubre todo el plano, satisfaciendo los dos requisitos de la definición de una ε-red.

Definiciones

Si (M,d) es un espacio métrico, y X es un subconjunto de M, entonces el radio de empaquetado de X es la mitad de la mínima de las distancias entre miembros distintos de X. Si el radio de empaquetamiento es r, entonces todas las bolas abiertas de radio r centradas en los puntos de X serán disjuntas entre sí, y cada bola abierta centrada en uno de los puntos de X con radio 2r será disjunta con respecto al resto de puntos de X. El radio de recubrimiento 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; esto es, es el radio más pequeño tal que la unión de las bolas cerradas de este radio centrado en los puntos de X contiene todo M. Un ε-empaquetado es un conjunto X de radios de empaquetado ≥ ε/2 (o lo que es lo mismo, con distancia mínima ≥ ε), un ε-recubrimiento es un conjunto X de radio de recubrimiento ≤ ε, y una ε-red es un conjunto que es a la vez un ε-empaquetado y un ε-recubrimiento. Un conjunto es uniformemente discreto si tiene un empaquetado de radio no nulo, y relativamente denso si tiene un radio de cobertura finito. Un conjunto de Delaunay es a la vez uniformemente discreto y relativamente denso; así, toda ε-red es un conjunto de Delaunay, pero no al revés.^[1]​^[2]​

Construcción de ε-redes

Siendo la más restrictiva de las definiciones anteriores, ε-redes son al menos tan difíciles de construir como los ε-empaquetados, los ε-recubrimientos, y los conjuntos de Delaunay. Aun así, siempre que los puntos de M son un conjunto bien ordenado, por un proceso de inducción transfinita es posible construir una ε-red N, incluyendo en N cada punto para el que la mínima de las distancias al conjunto de los anteriores puntos en la ordenación es al menos ε. Para conjuntos finitos de puntos en un espacio euclidiano de dimensión acotada, cada punto puede ser analizado en un tiempo finito localizándolo en una retícula de células de diámetro ε, utilizando un tabla hash para comprobar qué células cercanas ya contienen puntos de N; así, en este caso, una ε-red puede ser construida en un tiempo lineal.^[3]​^[4]​

Para espacios métricos finitos o compactos más generales, un algoritmo alternativo es el de Teo González, basado en el criterio del primer recorrido más lejano, que suele usarse para construir ε-redes finitas. Este algoritmo inicializa la red N vacía, añadiendo iterativamente a N el punto más lejano de M a N, rompiendo enlaces arbitrariamente y deteniéndose cuando todos los puntos de M quedan dentro de la distancia ε de N.^[5]​ En espacios de dimensión duplicada delimitada, el algoritmo de González puede ser implementado en un tiempo de O(n log n) para conjuntos de puntos con una proporción polinómica entre sus distancias más lejanas y más cercanas, y aproximadamente en el mismo límite de tiempo para conjuntos de puntos arbitrarios.^[6]​

Aplicaciones

Teoría de codificación

En la teoría de códigos de corrección de errores, el espacio métrico contiene un código de bloque C que consta de cadenas de una longitud fija, por ejemplo n, formadas sobre un alfabeto de q elementos (pueden ser visualizados como vectores), con la métrica de Hamming. Este espacio se denota como ${\displaystyle \scriptstyle {\mathcal {A}}_{q}^{n}}$ . El radio de recubrimiento y de empaquetado de este espacio métrico está relacionado con la capacidad de corregir errores del código.

Algoritmos de aproximación

Har-Peled y Raichel (2013) & Raichel (2013) describieron un paradigma algorítmico que denominaron "red y ciruela pasa" 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 trabaja siguiendo los pasos siguientes:

1. Escoger un punto aleatorio p del conjunto de puntos, encontrar su vecino más cercano q, y poner ε a la distancia entre p y q.
2. Probar si ε es (aproximadamente) mayor o menor que el valor de la solución óptima (utilizando una técnica específica para la optimización particular del problema que está siendo solucionado)
   • Si es mayor, eliminar de la entrada los puntos cuyo vecino más cercano es más lejano que ε
   • Si es más pequeño, construir una ε-red N, y eliminar de la entrada los puntos que no están en N.

En ambos casos, el número esperado de puntos restantes decrece por un factor constante, así que el tiempo de cálculo pasa a estar dominado por intervalo invertido en el paso de la prueba. Como demuestran, este paradigma se suele poder utilizar para construir algoritmos de aproximación rápida para nubes de k-centros, encontrando un par de puntos con distancia media, y resolver muchos otros problemas relacionados.

Un sistema jerárquico de redes, denominado una red-árbol, puede ser utilizado en espacios de dimensión duplicada delimitada para construir descomposiciones bien separadas, geometrías llave (geometric spanners), y en la búsqueda aproximada de puntos vecinos más cercanos.^[6]​^[7]​

Cristalografía

Para puntos en un espacio euclídeo, un conjunto X es un conjunto de Meyer si es relativamente denso y su conjunto de diferencias X − X es uniformemente discreto. De forma equivalente, X es un conjunto de Meyer si ambos X y X − X son conjuntos de Delaunay. Los conjuntos de Meyer deben su denominación a 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 en retículas, teselaciones de Penrose, y las sumas de Minkowski de estos conjuntos con conjuntos finitos.^[8]​

Referencias

1. Clarkson, Kenneth L. (2006), «Building triangulations using ε-nets», STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 326-335, doi:10.1145/1132516.1132564 ..
2. Some sources use "ε-net" for what is here called an "ε-covering"; see, e.g.
3. Har-Peled, S. (2004), «Clustering motion», Discrete and Computational Geometry 31 (4): 545-565, doi:10.1007/s00454-004-2822-7 ..
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 ..
5. González, T. F. (1985), «Clustering to minimize the maximum intercluster distance», Theoretical Computer Science 38 (2-3): 293-306, doi:10.1016/0304-3975(85)90224-5 ..
6. Har-Peled, S.; Mendel, M. (2006), «Fast construction of nets in low-dimensional metrics, and their applications», SIAM Journal on Computing 35 (5): 1148-1184, doi:10.1137/S0097539704446281 ..
7. Krauthgamer, Robert; Lee, James R. (2004), «Navigating nets: simple algorithms for proximity search», Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04), Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 798-807, ISBN 0-89871-558-X ..
8. 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 Academic Publishers, pp. 403-441 ..

Enlaces externos

• – Tilings Encyclopedia

•   Datos: Q5254313