Búsqueda de rango

En la búsqueda de rango ortogonal, el conjunto S consta de${\displaystyle n}$puntos en${\displaystyle d}$dimensiones, y la consulta consiste en intervalos en cada una de esas dimensiones. Por lo tanto, la consulta consiste en un rectángulo multidimensional alineado con los ejes . Con un tamaño de salida de${\displaystyle k}$, Jon Bentley utilizó un árbol kd para lograr (en notación Big O )${\displaystyle O(n)}$espacio y${\displaystyle O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}}$tiempo de consulta. ^{[ 2 ]} Bentley también propuso usar árboles de rango , lo que mejoró el tiempo de consulta a${\displaystyle O(\log ^{d}n+k)}$pero mayor espacio para${\displaystyle O(n\log ^{d-1}n)}$. ^{[ 3 ]} Dan Willard utilizó downpointers, un caso especial de cascada fraccionaria para reducir aún más el tiempo de consulta a${\displaystyle O(\log ^{d-1}n+k)}$. ^{[ 4 ]}

Si bien los resultados anteriores se lograron en el modelo de máquina de punteros , se han realizado mejoras adicionales en el modelo de RAM de palabras de computación en dimensiones bajas (2D, 3D, 4D). Bernard Chazelle utilizó árboles de rango comprimido para lograr${\displaystyle O(\log n)}$tiempo de consulta y${\displaystyle O(n)}$espacio para el conteo de rangos. ^{[ 5 ]} Joseph JaJa y otros mejoraron posteriormente este tiempo de consulta a${\displaystyle O\left({\dfrac {\log n}{\log \log n}}\right)}$para el conteo de rangos, que coincide con un límite inferior y, por lo tanto, es asintóticamente óptimo . ^{[ 6 ]}

A partir de 2015, los mejores resultados (en dimensiones bajas (2D, 3D, 4D)) para la presentación de informes de rango encontrados por Timothy M. Chan , Kasper Larsen y Mihai Pătrașcu , también utilizando árboles de rango comprimidos en el modelo de computación Word RAM, son uno de los siguientes: ^{[ 7 ]}

• ${\displaystyle O(n)}$espacio,${\displaystyle O(\log ^{\epsilon }n+k\log ^{\epsilon }n)}$tiempo de consulta
• ${\displaystyle O(n\log \log n)}$espacio,${\displaystyle O(\log \log n+k\log \log n)}$tiempo de consulta
• ${\displaystyle O(n\log ^{\epsilon }n)}$espacio,${\displaystyle O(\log \log n+k)}$tiempo de consulta

En el caso ortogonal, si uno de los límites es infinito , la consulta se denomina trilateral. Si dos de los límites son infinito, la consulta es bilateral, y si ninguno de los límites es infinito, entonces la consulta es tetralateral.

Mientras que en la búsqueda de rango estático el conjunto S se conoce de antemano, en la búsqueda de rango dinámico se permiten inserciones y eliminaciones de puntos. En la versión incremental del problema, solo se permiten inserciones, mientras que la versión decremental solo permite eliminaciones. Para el caso ortogonal, Kurt Mehlhorn y Stefan Näher crearon una estructura de datos para la búsqueda de rango dinámico que utiliza cascada fraccionaria dinámica para lograr${\displaystyle O(n\log n)}$espacio y${\displaystyle O(\log n\log \log n+k)}$tiempo de consulta. ^{[ 8 ]} Tanto las versiones incrementales como decrementales del problema se pueden resolver con${\displaystyle O(\log n+k)}$tiempo de consulta, pero se desconoce si se puede realizar una búsqueda de rango dinámico general con ese tiempo de consulta.

El problema del conteo de rangos coloreados considera el caso en que los puntos tienen atributos categóricos . Si las categorías se consideran como colores de puntos en el espacio geométrico, entonces una consulta es cuántos colores aparecen en un rango particular. Prosenjit Gupta y otros describieron una estructura de datos en 1995 que resolvió el conteo de rangos coloreados ortogonales 2D en${\displaystyle O(n^{2}\log ^{2}n)}$espacio y${\displaystyle O(\log ^{2}n)}$tiempo de consulta. ^{[ 9 ]} Esto se generalizó posteriormente a dimensiones superiores. ^{[ 10 ]}