3.1 Algoritmos basados en el método logarítmico
Los primeros algoritmos se basan en aplicar el método logarítmico de Bentley . Esta aplicación apareció por primera vez en Smid . (Ver también Schwarz .)
Sea S el conjunto actual de puntos en ℝD, y denote n su tamaño. Escribe n en el sistema numérico binario, n=∑i≥0ai2i, donde ai ∈ {0,1}. Particionar S (arbitrariamente) en subconjuntos: para cada i tal que ai = 1 hay un subconjunto Si, de tamaño 2i. Además, para cada tal i, hay un número real δi tal que d(S) ≤ δi ≤ d (Si) la estructura de datos consiste en lo siguiente.
(1)
El par más cercano de S y su distancia δ
(2)
Para cada i tal que ai = 1, un δi -grid que almacena los puntos de Si. Suponemos que las celdas no vacías de esta rejilla se almacenan en un árbol de búsqueda binario equilibrado, ordenado lexicográficamente según sus esquinas «inferiores izquierdas».
Consideremos ahora la inserción de un nuevo punto p. Para cada i tal que ai = 1, encontramos la celda de la rejilla δi que contiene a p junto con las 3D – 1 celdas vecinas. A continuación, calculamos las distancias entre p y todos los puntos de Si que están contenidos en estas celdas. Si encontramos una distancia menor que δ, entonces actualizamos δ, y el par más cercano. Queda por actualizar el resto de la estructura de datos. Sea j el índice tal que a0 = a1 = … = aj – 1 y aj = 0. Sea Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 y δj := δ. Construimos una rejilla δj para el conjunto Sj, y descartamos las rejillas del conjunto S0, S1,… Sj – 1 (con lo que implícitamente estos conjuntos quedan vacíos).
Para demostrar la corrección de este algoritmo, nótese que como d(S) ≤ δi, basta con comparar p con todos los puntos de Si que están en la vecindad de p- en la rejilla δi. Por lo tanto, el par más cercano se actualiza correctamente. Además, el nuevo valor Sj satisface d(S ∪ {p}) ≤ δj ≤ d(Sj), y para todo i > j, tenemos d(S ∪ {p} ≤ δi d(Si). Finalmente, la estructura de datos actualizada contiene una rejilla que almacena 2i puntos para cada i tal que la representación binaria de n + 1 contiene un uno en la posición i.
Analizamos la complejidad del algoritmo de inserción. En primer lugar, observe que, dado que δi ≤ d(Si), la vecindad de p en la rejilla δi contiene como mucho un número constante de puntos de Si. Por lo tanto, gastamos O(log n) de tiempo para cada cuadrícula. Dado que la estructura de datos contiene un número logarítmico de cuadrículas, la primera parte del algoritmo de inserción requiere un tiempo O(log 2n).
Consideremos la segunda parte del algoritmo, en la que construimos la cuadrícula δj. Este paso lleva O(|Sj |log |Sj|) de tiempo, debido a la ordenación. Sin embargo, si almacenamos los puntos en un orden adecuado, esta cuadrícula puede construirse en O(|Sj|) = O(2j). (Véase para más detalles.) Como j puede tomar cualquier valor entre cero y ⌊log n⌋, el tiempo de inserción fluctúa mucho. Afirmamos, sin embargo, que el tiempo amortizado para el segundo paso está acotado por O(log n).
Para demostrar esta afirmación, supongamos que empezamos con un conjunto vacío S y realizamos una secuencia de n inserciones. Sea kj el número de veces que, durante estas inserciones, construimos una rejilla para un subconjunto de tamaño 2j Entonces kj es como máximo igual al número de enteros que constan como máximo de 1 + ⌊log n⌋ bits cuyos j bits menos significativos son iguales a uno, y cuyo (j + 1)-primer bit es igual a cero. Es decir, tenemos
El tiempo total empleado para el segundo paso durante las n inserciones está acotado por
lo que demuestra la afirmación.
Hemos demostrado que el tiempo de ejecución del algoritmo completo para mantener el par más cercano está acotado por O(log 2n) tiempo en el peor caso más O(log n) tiempo amortizado por inserción. Utilizando técnicas estándar (véase Overmars ), podemos transformar la estructura de datos de tal manera que el segundo paso tome un tiempo logarítmico en el peor de los casos. Por lo tanto, tenemos una estructura de datos que mantiene el par más cercano en O(log 2n) de tiempo en el peor de los casos por inserción. La estructura tiene un tamaño O(n).
Nótese que el primer paso del algoritmo lleva un tiempo O(log 2n), mientras que el segundo paso sólo lleva un tiempo O(log n). Esto sugiere que es posible una mejora. En efecto, en lugar de escribir n en el sistema numérico binario, utilizamos el sistema numérico de base log n. (Ver Overmars o Schwarz .) De esta manera, ambos pasos toman O(log 2n/log log n) tiempo, mientras que el espacio utilizado sigue siendo lineal.
Por lo tanto, tenemos una estructura de datos de tamaño lineal que mantiene el par más cercano en O(log2 n /log log n) tiempo en el peor de los casos por inserción. Nótese que el algoritmo utiliza la función suelo para encontrar la celda de la rejilla que contiene el nuevo punto p. Reemplazando la rejilla por una rejilla degradada, el algoritmo puede implementarse en el modelo de árbol de cálculo algebraico.
Todavía es posible mejorar la estructura de datos anterior. Consideremos de nuevo la estructura de datos basada en la representación de n en el sistema numérico binario. La principal observación es la siguiente: Si insertamos un punto p, entonces para cada i tal que ai = 1, encontramos la celda de la faja δi que contiene a p (más las celdas vecinas). Es decir, realizamos consultas de localización de puntos en un número logarítmico de cuadrículas, pero siempre con el mismo punto de consulta p. En Schwarz y Smid , se demuestra que la técnica de cascada fraccionaria puede extenderse para que todas estas consultas juntas puedan resolverse en tiempo O(log n log n). El principal problema es que tenemos mallas con diferentes tamaños de malla. Por lo tanto, hay que introducir un ordenamiento en las celdas de la malla que sea «compatible» con todos estos tamaños. En tal ordenamiento se define. Como resultado, localizar el punto p en todas las mallas requiere O(log n) comparaciones. Sin embargo, como la ordenación es bastante complicada, cada comparación requiere un tiempo O(log n). En general, obtenemos una estructura de datos de tamaño O(n) que mantiene el par más cercano en tiempo amortizado O(log n log n) por inserción. Nótese que necesitamos la función floor para este resultado. Probablemente, esto puede hacerse en el peor de los casos, pero los detalles serán tediosos. No está claro si el ordenamiento en las celdas de la cuadrícula también puede definirse si utilizamos cuadrículas degradadas en lugar de cuadrículas estándar.
Por último, mencionamos una extensión de la estructura de datos anterior. La estructura descrita anteriormente utiliza en gran medida el hecho de que sólo insertamos puntos. Resulta, sin embargo, que la estructura puede ser adaptada para tratar con actualizaciones semi-online, como las definidas por Dobkin y Suri . Una secuencia de actualizaciones se llama semi-en línea si las inserciones son en línea – es decir, llegan en un orden desconocido – pero cuando se inserta un punto, se nos dice después de cuántas actualizaciones desde el momento de la inserción será borrado. Esta información adicional sobre las eliminaciones puede utilizarse para garantizar que, cuando se elimine un punto, siempre esté contenido en una cuadrícula que almacene un pequeño subconjunto. Como en un borrado la distancia mínima puede aumentar, almacenamos información extra en la estructura de datos para actualizar el par más cercano de forma eficiente. De este modo, obtenemos una estructura de datos de tamaño O(n) que mantiene el par más cercano en tiempo O(log 2n) en el peor de los casos por actualización semilínea. Para más detalles, remitimos al lector a Dobkin y Suri y Smid.