En geometría computacional, una descomposición en pares bien separados (WSPD por las iniciales de su nombre en inglés, Well-separated pair decomposition) de un conjunto de puntos es una secuencia de pares de conjuntos , de tal manera que cada par está bien separado, y para cada par de puntos distintos , existe precisamente un par que los separa.
El grafo inducido por una descomposición en pares bien separados puede servir como k-extensor del grafo euclídeo completo, y es útil para aproximar soluciones a diversos problemas relacionados con este caso.
Definición
Sean dos conjuntos disjuntos de puntos en , siendo la caja delimitadora mínima alineada con los ejes para los puntos en , y el factor de separación.
Se considera que y están bien separados si para cada y existe una d-bola de radio que contiene a cada uno, de manera que la distancia mínima entre las dos esferas sea de al menos .
Se considera ahora que una secuencia de pares bien separados de subconjuntos de , constituye una descomposición de pares bien separados (WSPD) de si para cualesquiera dos puntos distintos , existe precisamente un , , tal que:
y , o y .
Construcción
Árbol de división
Mediante la generación de un árbol de división justa, es posible construir una WSPD de tamaño en tiempo .
El principio general del árbol de división de un conjunto de puntos consiste en que cada nodo del árbol representa un conjunto de puntos y que el cuadro delimitador de se divide en su lado más largo en dos partes iguales, que forman los dos hijos de y su conjunto de puntos. Este proceso se repite recursivamente hasta que solo queda un punto en el conjunto.
Sea el tamaño del intervalo más largo del hiperrectángulo delimitador del conjunto de puntos y sea el tamaño de la dimensión i del hiperrectángulo delimitador del conjunto de puntos . A continuación, se presenta el pseudocódigo para el cálculo del árbol de división.
Let be the node for if // is a hyperrectangle which each side has a length of zero. Store in the only point in S. else Compute Let the i-th dimension be the one where Split along the i-th dimension in two same-size hyperrectangles and take the points contained in these hyperrectangles to form the two sets and .
Store and as, respectively, the left and right children of .
return
Este algoritmo se ejecuta en tiempo .
A continuación, se presenta un algoritmo más eficiente que se ejecuta en tiempo. El objetivo es recorrer la lista con solo operaciones por paso de la recursión, pero llamando a la recursión solo en la mitad de los puntos en cada iteración.
Sea la coordenada i del punto j en , de modo que esté ordenado según la coordenada i, y el punto. Además, sea el hiperplano que divide en dos el lado más largo de . Aquí está el algoritmo en pseudocódigo:
if // is a hyperrectangle which each side has a length of zero. Store in the only point in . else
repeat Compute
Let the i-th dimension be the one where
while and
Let and be respectively, the left and right children of . if
else if
until
Para mantener las listas ordenadas de cada nodo, se utilizan listas enlazadas. Se conservan punteros cruzados entre cada lista para poder recuperar un punto en tiempo constante. En el algoritmo anterior, en cada iteración del bucle, se realiza una llamada recursiva. En realidad, para reconstruir la lista sin la sobrecarga de reordenar los puntos, es necesario reconstruir las listas ordenadas una vez que todos los puntos se hayan asignado a sus nodos. Para reconstruir, se recorre cada lista en cada dimensión, se añade cada punto a la lista correspondiente de sus nodos y se agregan punteros cruzados a la lista original para poder agregar los punteros cruzados a las nuevas listas. Finalmente, se llama a la recursión en cada nodo y su conjunto.
Cálculo de WSPD
El WSPD se puede extraer de un árbol dividido mediante la llamada a la función recursiva en los hijos de cada nodo del árbol dividido. Sea / el conjunto de nodos hijos del nodo . A continuación, se presenta el pseudocódigo de la función .
FindWSPD(T, s) for each node u that is not a leaf in the split tree T do FindPairs(ul, ur)
A continuación, se presenta el pseudocódigo de la función .
FindPairs(v, w) if and are well-separated with respect to report else if( ) Recursively call and else Recursively call and
La combinación de los pares bien separados de todas las llamadas a proporciona el WSPD para la separación .
Cada vez que el árbol de recursión se divide en dos, se añade un par más a la descomposición. Así pues, el tiempo de ejecución del algoritmo depende del número de pares en la descomposición final.
Callahan y Kosaraju demostraron que este algoritmo encuentra una descomposición en pares bien separados (WSPD) de tamaño .
Propiedades Lema 1: Sea un par bien separado con respecto a . Sean y . Entonces, .
Demostración: Dado que y pertenecen al mismo conjunto, se tiene que , donde es el radio del círculo que encierra a y . Dado que y pertenecen a dos conjuntos bien separados, entonces . Se obtiene que:
Lema 2: Sea un par bien separado con respecto a . Sean y . Entonces, .
Demostración: Por la descomposición en pares bien separados (la desigualdad triangular), se tiene que:
Del Lema 1, se deduce que:
Aplicaciones La descomposición en pares bien separados (WSPD) tiene aplicaciones en la resolución de diversos problemas. Se puede utilizar para:
Resolver la problema del par de puntos más cercanos en tiempo . Resolver el problema de los k pares más cercanos en tiempo . Resolver el problema de los k pares más cercanos en tiempo . Resolver la problema de todos los vecinos más cercanos en tiempo . Proporcionar una -aproximación del diámetro de un conjunto de puntos en tiempo . Inducir directamente un t-expansor de un conjunto de puntos. Proporcionar una aproximación t del árbol de extensión mínima euclídea en d dimensiones en tiempo . Proporcionar una aproximación del árbol de extensión mínima euclídea en d dimensiones en tiempo .
Referencias
Categoría:Geometría computacional