Búsqueda de rango

Búsqueda de rango simplex.

En informática , el problema de búsqueda de rango consiste en procesar un conjunto S de objetos, con el fin de determinar qué objetos de S se intersecan con un objeto de consulta, llamado rango . Por ejemplo, si S es un conjunto de puntos que corresponden a las coordenadas de varias ciudades, encuentre el subconjunto de ciudades dentro de un rango dado de latitudes y longitudes .

El problema de búsqueda de rangos y las estructuras de datos que lo resuelven son un tema fundamental de la geometría computacional . Las aplicaciones del problema surgen en áreas como los sistemas de información geográfica (GIS), el diseño asistido por computadora (CAD) y las bases de datos .

Variaciones

Existen diversas variantes del problema y pueden ser necesarias distintas estructuras de datos para cada una de ellas. ^[1] Para obtener una solución eficiente, es necesario especificar varios aspectos del problema:

• Tipos de objetos: Los algoritmos dependen de si S consta de puntos , líneas , segmentos de línea , cajas , polígonos ... Los objetos más simples y estudiados para buscar son los puntos.
• Tipos de rangos: los rangos de consulta también deben extraerse de un conjunto predeterminado. Algunos conjuntos de rangos bien estudiados y los nombres de los problemas respectivos son rectángulos alineados con el eje (búsqueda de rangos ortogonales), simples , medios espacios y esferas / círculos .
• Tipos de consulta: Si se debe informar la lista de todos los objetos que intersecan el rango de consulta, el problema se denomina informe de rango y la consulta se denomina consulta de informe . A veces, solo se requiere la cantidad de objetos que intersecan el rango. En este caso, el problema se denomina recuento de rango y la consulta se denomina consulta de recuento . La consulta de vacío informa si hay al menos un objeto que interseca el rango. En la versión de semigrupo , se especifica un semigrupo conmutativo ( S ,+), a cada punto se le asigna un peso de S y se requiere informar la suma del semigrupo de los pesos de los puntos que intersecan el rango.
• Búsqueda de rango dinámico vs. búsqueda de rango estático: en la configuración estática, el conjunto S se conoce de antemano. En la configuración dinámica, los objetos se pueden insertar o eliminar entre consultas.
• Búsqueda de rango fuera de línea: tanto el conjunto de objetos como el conjunto completo de consultas se conocen de antemano.

Estructuras de datos

Búsqueda de rango ortogonal

Una consulta de rango ortogonal 2D. En este caso, una consulta de informe de rango devolvería los dos puntos marcados con un círculo, una consulta de conteo de rango devolvería 2 y una consulta de vacío devolvería falso.

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

Si bien los resultados anteriores se lograron en el modelo de máquina de puntero , 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 rangos comprimidos para lograr tiempo y espacio de consulta para el conteo de rangos. ^[5] Joseph JaJa y otros mejoraron posteriormente este tiempo de consulta para el conteo de rangos, que coincide con un límite inferior y, por lo tanto, es asintóticamente óptimo . ^[6] ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O\left({\dfrac {\log n}{\log \log n}}\right)}$

A partir de 2015, los mejores resultados (en dimensiones bajas (2D, 3D, 4D)) para 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 cálculo Word RAM, son uno de los siguientes: ^[7]

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

En el caso ortogonal, si uno de los límites es infinito , la consulta se denomina de tres lados. Si dos de los límites son infinitos, la consulta es de dos lados y, si ninguno de los límites es infinito, la consulta es de cuatro lados.

Búsqueda de rango dinámico

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 espacio y tiempo de consulta. ^[8] Tanto la versión incremental como la decremental del problema se pueden resolver con tiempo de consulta, pero se desconoce si la búsqueda de rango dinámico general se puede realizar con ese tiempo de consulta. ${\displaystyle O(n\log n)}$ ${\displaystyle O(\log n\log \log n+k)}$ ${\displaystyle O(\log n+k)}$

Búsqueda de rango de colores

El problema del conteo de rangos de colores considera el caso en el 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 sobre 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 de colores ortogonales 2D en el espacio y el tiempo de consulta. ^[9] ${\displaystyle O(n^{2}\log ^{2}n)}$ ${\displaystyle O(\log ^{2}n)}$

Aplicaciones

Además de tenerse en cuenta en la geometría computacional , la búsqueda de rangos, y en particular la búsqueda de rangos ortogonales, tiene aplicaciones para consultas de rangos en bases de datos . La búsqueda de rangos coloreados también se utiliza para buscar datos categóricos y está motivada por ellos. Por ejemplo, determinar las filas en una base de datos de cuentas bancarias que representan a personas cuya edad está entre 25 y 40 años y que tienen entre $10000 y $20000 podría ser un problema de informe de rangos ortogonales donde la edad y el dinero son dos dimensiones.

Véase también

• Árbol de distribución
• Consulta de rango

Referencias

1. Agarwal, PK ; Erickson, J. (1999), "Búsqueda de rangos geométricos y sus parientes", en Chazelle, Bernard ; Goodman, Jacob ; Pollack, Richard (eds.), Avances en geometría discreta y computacional: actas de la conferencia de investigación de verano conjunta AMS-IMS-SIAM de 1996, Geometría discreta y computacional: diez años después, 14-18 de julio de 1996, Mount Holyoke College , Contemporary Mathematics, vol. 223, American Mathematical Society Press, págs. 1–56
2. Bentley, Jon (1975). "Árboles de búsqueda binaria multidimensionales utilizados para búsqueda asociativa". Comunicaciones de la ACM . 18 (9): 509–517. doi : 10.1145/361002.361007 . S2CID  13091446.
3. Bentley, Jon (1980). "Divide y vencerás multidimensional". Comunicaciones de la ACM . 23 (4): 214–229. doi : 10.1145/358841.358850 . S2CID  3997186.
4. Willard, Dan (1985). "Nuevas estructuras de datos para consultas de rango ortogonal". Revista SIAM de Computación . 14 (1): 232–253. doi :10.1137/0214019.
5. Chazelle, Bernard (1988). "Un enfoque funcional de las estructuras de datos y su uso en la búsqueda multidimensional". Revista SIAM de Informática . 17 (3): 427–462. CiteSeerX 10.1.1.133.9153 . doi :10.1137/0217026. 
6. JaJa, Joseph; Mortensen, Christian; Shi, Qingmin (2005). "Algoritmos rápidos y con uso eficiente del espacio para el conteo e informe de dominancia multidimensional". Simposio internacional sobre algoritmos y computación : 558–568.
7. Chan, Timothy ; Larsen, Kasper; Pătrașcu, Mihai (2011). "Búsqueda de rango ortogonal en la RAM, revisitada". Simposio sobre geometría computacional : 1–10. arXiv : 1103.5510 .
8. Mehlhorn, Kurt ; Näher, Stefan (1990). "Cascada fraccionada dinámica" (PDF) . Algorítmica . 5 (2): 215–241. doi :10.1007/BF01840386. S2CID  7721690.
9. Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1995). "Resultados adicionales sobre problemas generalizados de búsqueda de intersecciones: recuento, generación de informes y dinamización". Journal of Algorithms . 19 (2): 282–317. doi :10.1006/jagm.1995.1038. hdl : 11858/00-001M-0000-0014-B721-F .

Lectura adicional

• de Berg, Mark; van Kreveld, Marc; Overmars, Marcos ; Schwarzkopf, Otfried (2000), Geometría computacional (2ª ed.), Berlín: Springer-Verlag, ISBN 3-540-65620-0
• Matoušek, Jiří (1994), "Búsqueda de rango geométrico", ACM Computing Surveys , 26 (4): 421–461, doi :10.1145/197405.197408, S2CID  17729301.