Conjunto Delaunay

En la teoría de espacios métricos , -nets , -packings , -coverings , conjuntos uniformemente discretos , conjuntos relativamente densos y conjuntos de Delaunay (llamados así por el matemático soviético Boris Nikolayevich Delaunay ) son definiciones estrechamente relacionadas de conjuntos de puntos, y el radio de empaquetamiento y El radio de cobertura [1] de estos conjuntos determina qué tan bien están espaciados los puntos de estos conjuntos. 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 de un conjunto X es la mitad de su mínimo de distancias entre distintos puntos de X. Si el radio de empaque es r , entonces las bolas abiertas de radio r centradas en los puntos X no se intersecan, y cualquier bola abierta centrada en un punto en X con radio 2 r no contiene otros puntos de X. El radio de cobertura de un conjunto X es el mínimo de números r tal que cualquier punto en M está a una distancia r o menor de al menos un punto en X. Es decir, es el radio más pequeño tal que la unión de bolas cerradas de este radio con centros en el conjunto X es igual al espacio M . Un conjunto X es un empaque si el radio de empaque es /2 (equivalentemente, la distancia mínima es ), una cubierta es un conjunto X con radio de cobertura y una red es un conjunto que es a la vez un empaque y un - cubrir _ Un conjunto se llama uniformemente discreto si tiene un radio de empaquetamiento distinto de cero y relativamente denso si tiene un radio de cobertura finito. Un conjunto de Delaunay es un conjunto uniformemente discreto y relativamente denso. Entonces cualquier -net es un conjunto de Delaunay, pero lo contrario no es cierto [2] [3] [4] .

Sistemas y cristales correctos

Un conjunto de Delaunay se llama sistema regular si su grupo de simetría G actúa transitivamente sobre el conjunto X (es decir, X es la órbita G de un punto). Un conjunto de Delaunay se llama cristal si X es la órbita G de algún conjunto finito. El sistema correcto es un caso especial importante de un cristal [1] .

  1. En el plano, cualquier conjunto de Delaunay en el que todos los barrios 4R sean equivalentes es un sistema regular.
  2. En un espacio de cualquier dimensión, el valor de 4R es inmejorable
  3. En el espacio 3D, cualquier conjunto de Delaunay en el que todos los grupos 10R sean equivalentes es un sistema regular.
  4. En un espacio de cualquier dimensión, existe un límite superior para un radio tal que la identidad de los grupos de un radio dado en el conjunto de Delaunay garantiza su corrección [5] .

Construcción de redes épsilon

Como definición con la mayoría de las restricciones, las redes no son más fáciles de construir que los empaques , las cubiertas y los conjuntos de Delaunay. Sin embargo, si los puntos del conjunto M son un conjunto bien ordenado , la inducción transfinita muestra que es posible construir un -net N , incluyendo en N todo punto para el cual el mínimo de distancias al conjunto de puntos precedentes está en orden al menos Dado un conjunto finito de puntos en un espacio euclidiano de dimensión limitada, cada punto se puede verificar en tiempo constante asignando celdas de diámetro a una red y usando una tabla hash para verificar qué celdas vecinas ya contienen N puntos . Por lo tanto, -network se puede construir en tiempo lineal [6] [7] .

Para espacios métricos finitos o compactos más generales, el algoritmo alternativo de Teófilo González , basado en la selección de los puntos más externos , puede usarse para construir una red finita . Este algoritmo comienza con una red vacía N y agrega a N el punto más alejado de N de M , rompiendo arbitrariamente las conexiones, y se detiene cuando todos los puntos de M están a una distancia de N [8] . En espacios de dimensión de duplicación limitada , se puede implementar el algoritmo de González con tiempo corrido para conjuntos de puntos con dependencia polinomial entre las distancias mayor y menor, así como un algoritmo de solución aproximada del problema con el mismo tiempo corrido y conjuntos arbitrarios. de puntos [9] .

Aplicaciones

Teoría de la codificación

Para un código C (un subconjunto de ), el radio de cobertura de C es el valor más pequeño de r tal que cualquier elemento está contenido en al menos una bola de radio r centrada en una palabra clave de C . El radio de empaquetamiento de C es el valor más grande de s tal que el conjunto de bolas de radio s con centro en C son disjuntos por pares. A partir de la prueba de la cota de Hamming, se puede obtener que para

.

Por lo tanto, y si se cumple la igualdad, entonces . El caso de igualdad significa que se ha alcanzado el límite de Hamming.

En la teoría del código de corrección , un espacio métrico que contiene un código de bloque C , consiste en cadenas de longitud constante, digamos n , sobre un alfabeto de tamaño q (puede pensarse como vectores ) con distancias de Hamming . Este espacio se denota como . El radio de cobertura y el radio de empaquetado de este espacio métrico están relacionados con la capacidad de los códigos para corregir errores.

Algoritmos de aproximación

Har-Peled y Rachel [10] describen un paradigma algorítmico que llaman "redes y poda" para desarrollar algoritmos de aproximación para ciertos tipos de problemas de optimización geométrica definidos en conjuntos de puntos en espacios euclidianos . Este tipo de algoritmo funciona siguiendo los siguientes pasos:

  1. Elegimos un punto p al azar de un conjunto de puntos, encontramos el vecino q más cercano y lo igualamos a la distancia entre p y q .
  2. Verificar si (aproximadamente) es mayor o menor que el valor óptimo (usando una técnica determinada por las especificaciones del problema de optimización que se está resolviendo)
    • Si el valor es mayor, eliminamos de los datos de entrada los puntos cuyos vecinos más cercanos están más lejos que
    • Si el valor es menor, construimos un -net N y eliminamos puntos de la entrada que no pertenecen a N .

En ambos casos, el número esperado de puntos restantes se reduce por un factor constante, de modo que el tiempo de ejecución se determina por el paso de prueba. Como demostraron, dicho paradigma se puede usar para construir algoritmos de aproximación rápida para encontrar el centro k , encontrar un par de puntos con una distancia promedio y algunos problemas relacionados.

Un sistema jerárquico de redes, llamado árbol de red , se puede utilizar en espacios de dimensión de duplicación acotada para construir pares de descomposición bien separados , extensiones geométricas y una solución aproximada del problema del vecino más cercano [9] [11] .

Cristalografía

Para puntos en el espacio euclidiano, un conjunto X es un conjunto de Meyer , si es relativamente denso y su diferencia de Minkowski es uniformemente discreta. De manera equivalente, X es un conjunto de Meyer si y X es un conjunto de Delaunay. 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 un modelo matemático para los cuasicristales . Incluyen conjuntos de puntos de red , mosaicos de Penrose y sumas de Minkowski de estos conjuntos finitos [12] .

Las celdas de Voronoi de los conjuntos simétricos de Delaunay forman poliedros que llenan el espacio, que se denominan plesioedros [13] .

Véase también

Notas

  1. ↑ 1 2 Dolbilin, 2016 , pág. 32.
  2. ↑ Clarkson, 2006 , pág. 326–335.
  3. ↑ Algunas fuentes usan el nombre " -red" para la estructura a la que se hace referencia en este artículo como " -cobertura". Véase, por ejemplo, Sutherland, 1975 , p. 110
  4. ↑ El propio Delaunay los llamó sistemas de conjuntos.
  5. ↑ Dolbilin, 2016 , pág. 32-33.
  6. ↑ Har-Peled, 2004 , pág. 545–565.
  7. ↑ Har-Peled, Raichel, 2013 , pág. 605–614.
  8. ↑ González, 1985 , p. 293–306.
  9. ↑ 1 2 Har-Peled, Mendel, 2006 , pág. 1148–1184.
  10. ↑ Har-Peled, Raichel, 2013 .
  11. ↑ Krauthgamer, Lee, 2004 , pág. 798–807.
  12. ↑ Moody, 1997 , pág. 403–441.
  13. ↑ Grünbaum y Shephard 1980 , p. 951–973.

Literatura

Enlaces