Descomposición de pares bien separados

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 los dos. $S\subconjunto \mathbb {R} ^{d}$ $(A_{i},B_{i})$ $p,q\en S$

El gráfico inducido por una descomposición de pares bien separados puede servir como un k-spanner del gráfico euclidiano completo y es útil para aproximar soluciones a varios problemas relacionados con esto. ^[1]

Definición

Sean dos conjuntos disjuntos de puntos en , denote el cuadro delimitador mínimo alineado al eje para los puntos en , y denote el factor de separación . ${\estilo de visualización A,B}$ $\mathbb {R} ^{d}$ ${\estilo de visualización R(X)}$ ${\estilo de visualización X}$ ${\estilo de visualización s>0}$

Consideramos que y están bien separados , si para cada uno de y existe una bola d de radio que lo contiene, tal que las dos esferas tienen una distancia mínima de al menos . ^[2] ${\estilo de visualización A}$ ${\estilo de visualización B}$ $R(A)$ ${\estilo de visualización R(B)}$ ${\estilo de visualización \rho}$ ${\estilo de visualización s\rho}$

Consideramos que una secuencia de pares bien separados de subconjuntos de , es una descomposición de pares bien separados (WSPD) de si para dos puntos distintos , existe precisamente un , , tal que ${\estilo de visualización S}$ $(A_{1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})$ ${\estilo de visualización S}$ $p,q\en S$ ${\estilo de visualización i}$ $1\leq i\leq m$

$p\in A_{i}$ y , o $q\en B_{i}$
$q\en A_{i}$ y . ^[1] $p\in B_{i}$

Construcción

Árbol dividido

Mediante la construcción de un árbol dividido justo, es posible construir un WSPD de tamaño en el tiempo. ^[2] $O(s^{d}n)$ $O(n\lg n)$

El principio general del árbol de división 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 hace 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.$ A continuación, presentamos un pseudocódigo para el cálculo del árbol de división.

 $SplitTree(S)$  Sea  $u$  el nodo de  $S$  si   $|S| = 1$   $R(u) := R(S)$  //  $R(S)$  es un hiperrectángulo cuyo lado tiene una longitud de cero. Almacena en  $u$  el único punto en S. de lo contrario Calcula  $R(S)$  Sea la dimensión i -ésima aquella donde  $L max (R(S)) = L i (R(S))$  Divide  $R(S)$  a lo largo de la dimensión i -ésima en dos hiperrectángulos del mismo tamaño y toma 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)$  Almacena  $v$  y  $w$  como, respectivamente, los hijos izquierdo y derecho de  $u$  .  $R(u) := R(S)$  devuelve   $u$

Este algoritmo se ejecuta en el tiempo. $Estilo de visualización O(n^{2})}$

A continuación, presentamos un algoritmo más eficiente que se ejecuta en el tiempo. El objetivo es recorrer la lista solo en operaciones por paso de la recursión, pero solo invocar la recursión en, como máximo, la mitad de los puntos cada vez. $O(n\lg n)$ $O(n)$

Sea $S i j$ la i -ésima coordenada del j -ésimo punto en $S$ tal que $S i$ esté ordenado según la i -ésima coordenada 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:

 $SplitTree(S, u)$  si   $|S| = 1$   $R(u) := R(S)$  //  $R(S)$  es un hiperrectángulo cuyo lado tiene una longitud de cero. Almacena en  $u$  el único punto en  $S.$ de lo contrario tamaño  $:= |S|$  repetir Calcular  $R(S)$   $R(u) := R(S)$   $j : = 1$   $k : = |S|$  Sea la dimensión i -ésima aquella donde  $L máx (R(S)) = L i (R(S))$   $S v : = \emptyset$   $S w : = \emptyset$  mientras   $S i j+1 < h(R(S))$  y   $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 < h(R(S))$   $S v  := S \ S w$   $u := v$   $S := S v$   $SplitTree(S w,w)$  hasta que   $tamaño ≤ .mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n ⁄ 2$   $SplitTree(S,u)$

Para poder mantener las listas ordenadas para cada nodo, se utilizan listas enlazadas. Se mantienen los puntos de cruce de cada lista con 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 recursión. En realidad, para poder reconstruir la lista sin la sobrecarga de reordenar los puntos, es necesario reconstruir las listas ordenadas una vez que todos los puntos se han asignado a sus nodos. Para hacer la reconstrucción, se recorre cada lista para cada dimensión, se añade cada punto a la lista correspondiente de sus nodos y se añaden los puntos de cruce en la lista original para poder añadir los puntos de cruce para las nuevas listas. Por último, 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 de este tipo llamando a la función recursiva $FindPairs(v,w)$ en los hijos de cada nodo del árbol dividido. Sea $u l$ / $u r$ los hijos del nodo $u$ . A continuación, proporcionamos un pseudocódigo para la función $FindWSPD(T, s) .$

FindWSPD(T, s) para cada nodo u que no sea una hoja en el árbol dividido T,  haga FindPairs(u _l , u _r )

A continuación proporcionamos un pseudocódigo para la función $FindPairs(v, w)$ .

FindPairs(v, w) si   $S v$  y  $S w$  están bien separados con respecto a  $s$  informe  $par(S v, S w)$  de lo contrario  si (  $L max (R(v)) \leq L max (R(w))$  ) Llamar recursivamente  $a FindPairs(v, w l)$  y  $FindPairs(v, w r)$  de lo contrario Llamar recursivamente  $a 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)$ proporciona el WSPD para la separación $s$ .

Cada vez que el árbol de recursión se divide en dos, se agrega un par más a la descomposición. Por lo tanto, el tiempo de ejecución del algoritmo se expresa en la cantidad 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] $O(s^{d}n)$

Propiedades

Lema 1 : Sea un par bien separado con respecto a . Sea y . Entonces, . ${\estilo de visualización \{A,B\}}$ ${\estilo de visualización s}$ $p,p'\en A$ $q\en B$ $|pp'|\leq (2/s)|pq|$

Demostración : Como y están en el mismo conjunto, tenemos que donde es el radio del círculo que encierra a y . Como y están en dos conjuntos bien separados, tenemos que . Obtenemos que: ${\estilo de visualización p}$ ${\estilo de visualización p'}$ $|pp'|\leq 2\rho$ ${\estilo de visualización \rho}$ ${\estilo de visualización A}$ ${\estilo de visualización B}$ ${\estilo de visualización p}$ ${\estilo de visualización q}$ $|pq|\geq s\rho$

${\begin{aligned}&{\frac {|pp'|}{2}}\leq \rho \leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&{\frac {|pp'|}{2}}\leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&|pp'|\leq {\frac {2}{s}}|pq|\\\end{aligned}}$

Lema 2 : Sea un par bien separado con respecto a . Sea y . Entonces, . $\{A,B\}$ $s$ $p,p'\in A$ $q,q'\in B$ $|p'q'|\leq (1+4/s)|pq|$

Demostración : Por la desigualdad triangular, tenemos:

$|p'q'|\leq |p'p|+|pq|+|qq'|$

Del Lema 1 obtenemos:

${\begin{aligned}|p'q'|&\leq (2/s)|pq|+|pq|+(2/s)|pq|\\&=(1+4/s)|pq|\end{aligned}}$

Aplicaciones

La descomposición en pares bien separados tiene aplicación en la solución de diversos problemas. WSPD se puede utilizar para:

Resolver el problema del par más cercano en el tiempo. ^[1] $O(n\lg n)$
Resolver el problema de los k pares más cercanos en el tiempo. ^[1] $O(n\lg n+k)$
Resolver el problema del k par más cercano en el tiempo. ^[3] $O(n\lg n)$
Resolver el problema de todos los vecinos más cercanos en el tiempo. ^[1] $O(n\lg n)$
Proporciona una aproximación del diámetro de un punto determinado en el tiempo. ^[1] $(1-\epsilon )$ $O(n\lg n)$
Inducir directamente una llave t de un conjunto de puntos. ^[1]
Proporcionar una aproximación t del árbol de expansión mínimo euclidiano en d dimensiones en el tiempo. ^[1] $O(n\lg n)$
Proporciona una aproximación del árbol de expansión mínimo euclidiano en d dimensiones en el tiempo. ^[4] $(1+\epsilon )$ $O(n\lg n+(\epsilon ^{-2}\lg ^{2}{\frac {1}{\epsilon }})n)$

Referencias

^ abcdefgh 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 .
^ abc Callahan, PB y Kosaraju, SR (enero de 1995). "Una descomposición de conjuntos de puntos multidimensionales con aplicaciones a k-vecinos más próximos y campos potenciales de n cuerpos". Revista de la ACM . 42 (1): 67–90. doi : 10.1145/200836.200853 .
^ Bespamyatnikh, Sergei; Segal, Michael (2002). "Algoritmos rápidos para aproximar distancias". Algorithmica . 33 (2): 263–269. doi :10.1007/s00453-001-0114-7. S2CID 9758120.
^ Arya, Sunil; Mount, David M. (2016). "Un algoritmo rápido y simple para calcular árboles de expansión euclidianos mínimos aproximados". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos : 1220-1233. doi :10.1137/1.9781611974331.ch85. ISBN: 978-0-2016-001-001 978-1-61197-433-1.