En geometría computacional , una descomposición de pares bien separados (WSPD) de un conjunto de puntos, es una secuencia de pares de conjuntos , de modo que cada par esté bien separado , y para cada dos puntos distintos, existe precisamente un par que separa a los dos.
El gráfico inducida por una descomposición par bien separado puede servir como una k-llave de la completa gráfico euclidiana , y es útil en aproximar soluciones a varios problemas relacionados con esto. [1]
Definición
Dejar ser dos conjuntos de puntos disjuntos en , denotar el cuadro delimitador mínimo alineado con el eje para los puntos en, y denotar el factor de separación .
Consideramos y estar bien separados , si para cada uno de y existe una d-ball de radio que lo contiene, de modo que las dos esferas tengan una distancia mínima de al menos . [2]
Consideramos una secuencia de pares bien separados de subconjuntos de , ser una descomposición de pares bien separados (WSPD) de si por dos puntos distintos , existe precisamente uno , , tal que o
- y , o
- y . [1]
Construcción
Árbol partido
Al construir un árbol dividido justo , es posible construir un WSPD de tamaño en hora. [2]
El principio general del árbol dividido de un conjunto de puntos S es que cada nodo u del árbol representa un conjunto de puntos S u y que el cuadro delimitador R (S u ) de S u se divide a lo largo de su lado más largo en dos partes iguales que forman los dos hijos de u y su conjunto de puntos. Se realiza de forma recursiva hasta que solo queda un punto en el conjunto.
Sea L max (R (X)) el tamaño del intervalo más largo del hiperrectángulo delimitador del conjunto de puntos X y sea L i (R (X)) el tamaño de la i -ésima dimensión del hiperrectángulo delimitador del conjunto de puntos X . Damos pseudocódigo para el cálculo del árbol dividido a continuación.
SplitTree (S) Sea u el nodo de S si | S | = 1 R (u): = R (S) // R (S) es un hiperrectángulo en el que cada lado tiene una longitud de cero. Almacene en u el único punto en S. de lo contrario Calcule R (S) Sea la i -ésima dimensión aquella en la que L max (R (S)) = L i (R (S)) Dividir R (S) a lo largo de i -ésima dimensión en dos hiperrectángulos del mismo tamaño y tome los puntos contenidos en estos hiperrectángulos para formar los dos conjuntos S v y S w . v: = SplitTree (S v ) w: = SplitTree (S w ) Almacene v y w como, respectivamente, los hijos izquierdo y derecho de u . R (u): = R (S) devuelve u
Este algoritmo se ejecuta en hora.
Damos un algoritmo más eficiente que se ejecuta en tiempo a continuación. El objetivo es recorrer la lista en solo operaciones por paso de la recursividad, pero solo invocan la recursividad en como máximo la mitad de los puntos cada vez.
Sea S i j la j -ésima coordenada del i -ésimo punto en S tal que S se ordena para cada dimensión y p (S i j ) sea el punto. Además, sea h (R (S)) el hiperplano que divide el lado más largo de R (S) en dos. Aquí está el algoritmo en pseudocódigo:
Árbol dividido (S, u) si | S | = 1 R (u): = R (S) // R (S) es un hiperrectángulo en el que cada lado tiene una longitud de cero. Almacenar en u el único punto en S . más tamaño: = | S | repetir Calcular R (S) R (u): = R (S) j: = 1 k: = | S | Sea la i -ésima dimensión aquella en la que L max (R (S)) = L i (R (S)) S v : = ∅ S w : = ∅ mientras que S i j + 1y S i k-1 > h (R (S)) tamaño: = tamaño - 1 S v : = S v ∪ {p (S_i ^ j) } S w : = S w ∪ {p (S_i ^ k) } j: = j + 1 k: = k - 1 Sean v y w , respectivamente, los hijos izquierdo y derecho de u . si S i j + 1 > h (R (S)) S w : = S \ S v u: = w S: = S w SplitTree (S v , v) de lo contrario si S i k-1 S v : = S \ S w u: = v S: = S v SplitTree (S w , w) hasta que el tamaño ≤ n ⁄ 2 SplitTree (S, u)
Para poder mantener las listas ordenadas para cada nodo, se utilizan listas enlazadas. Los punteros cruzados se mantienen para cada lista a las demás para poder recuperar un punto en tiempo constante. En el algoritmo anterior, en cada iteración del bucle, se realiza una llamada a la recursividad. En realidad, para poder reconstruir la lista sin la sobrecarga de recurrir a los puntos, es necesario reconstruir las listas ordenadas una vez que todos los puntos han sido asignados a sus nodos. Para hacer la reconstrucción, recorra cada lista para cada dimensión, agregue cada punto a la lista correspondiente de sus nodos y agregue punteros cruzados en la lista original para poder agregar los punteros cruzados para las nuevas listas. Finalmente, llame a la recursividad en cada nodo y su conjunto.
Cálculo WSPD
El WSPD se puede extraer de dicho árbol dividido llamando a la función recursiva FindPairs (v, w) en los hijos de cada nodo en el árbol dividido. Sea u l / u r los hijos del nodo u . Damos pseudocódigo para la función FindWSPD (T, s) a continuación.
FindWSPD (T, s) para cada nodo u que no sea una hoja en el árbol dividido T do FindPairs (u l , u r )
Damos pseudocódigo para la función FindPairs (v, w) a continuación.
FindPairs (v, w) si S v y S w están bien separados con respecto al par de informes s (S v , S w ) en caso contrario si ( L max (R (v)) ≤ L max (R (w)) ) Llame recursivamente FindPairs (v, w l ) y FindPairs (v, w r ) de lo contrario Llame recursivamente FindPairs (v l , w) y FindPairs (v r , w)
La combinación de los pares s bien separados de todas las llamadas de FindPairs (v, w) da el WSPD para la separación s .
Prueba de corrección del algoritmo. |
---|
Está claro que los pares devueltos por el algoritmo están bien separados debido a la condición de retorno de la función FindPairs . Ahora, tenemos que demostrar que para cualquier punto distinto y en , hay un par único para que (yo) y o (ii) y . Suponga sin pérdida de generalidad que (i) se cumple. Dejar ser el antepasado común más bajo de y en el árbol partido y dejar y ser los hijos de . Debido a la última suposición, está en el subárbol de y en el subárbol de . Una llamada a FindPairs (v, w) se realiza necesariamente en FindWSPD . Debido a que, cada vez que hay una recursividad, el árbol de recursividad crea dos ramas que contienen todos los puntos de la llamada recursiva actual, habrá una secuencia de llamada a FindPairs que llevará a tener en y en . Porque es el antepasado común más bajo de y , llamar a FindPairs en los hijos de un nodo superior resultaría de y no estar en un par y llamar a FindPairs en los hijos en uno de los nodos de uno de los subárboles de resultaría por o no estar en ningún par. Por lo tanto, la pareja es el único que separa y . |
Cada vez que el árbol de recursividad se divide en dos, se agrega un par más a la descomposición. Entonces, el tiempo de ejecución del algoritmo está en el número de pares en la descomposición final.
Callahan y Kosaraju demostraron que este algoritmo encuentra una descomposición de pares bien separados (WSPD) de tamaño . [2]
Propiedades
Lema 1 : Sea ser un par bien separado con respecto a . Dejar y . Luego,.
Prueba : Porque y están en el mismo conjunto, tenemos que dónde es el radio del círculo circundante de y . Porque y están en dos conjuntos bien separados, tenemos que . Obtenemos que:
Lema 2 : Sea ser un par bien separado con respecto a . Dejar y . Luego,.
Prueba : por la desigualdad del triángulo, tenemos:
Del Lema 1, obtenemos:
Aplicaciones
La descomposición de pares bien separados tiene aplicación para resolver una serie de problemas. WSPD se puede utilizar para:
- Resuelva el problema de par más cercano enhora. [1]
- Resuelva el problema de k pares más cercanos enhora. [1]
- Resuelva el problema de k pares más cercanos enhora. [3]
- Resuelva el problema de los vecinos más cercanos enhora. [1]
- Proporcionar una - aproximación del diámetro de un punto fijado enhora. [1]
- Induzca directamente una llave en T de un conjunto de puntos. [1]
- Proporcione una aproximación t del árbol de expansión mínimo euclidiano en d dimensiones enhora. [1]
- Proporcionar una -aproximación del árbol de expansión mínimo euclidiano en d dimensiones enhora. [4]
Referencias
- ↑ a b c d e f g h Smid, Michiel (16 de agosto de 2005). "La descomposición de pares bien separados y sus aplicaciones" (PDF) . Consultado el 26 de marzo de 2014 .
- ^ a b c Callahan, PB y Kosaraju, SR (enero de 1995). "Una descomposición de conjuntos de puntos multidimensionales con aplicaciones a k-vecinos más cercanos y campos de potencial n-cuerpo". Revista de la ACM . 42 (1): 67–90. doi : 10.1145 / 200836.200853 .
- ^ Bespamyatnikh, Sergei; Segal, Michael (2002). "Algoritmos rápidos para la aproximación de distancias". Algoritmica . 33 (2): 263–269. doi : 10.1007 / s00453-001-0114-7 .
- ^ Arya, Sunil; Monte, David M. (2016). "Un algoritmo rápido y simple para calcular árboles de expansión mínimos euclidianos aproximados". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos .