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 cruzan con un objeto de consulta, llamado rango . Por ejemplo, si S es un conjunto de puntos correspondientes a las coordenadas de varias ciudades, encuentre el subconjunto de ciudades dentro de un rango determinado 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 (SIG), el diseño asistido por computadora (CAD) y las bases de datos .

Variaciones

Hay varias variaciones del problema y pueden ser necesarias diferentes estructuras de datos para diferentes variaciones. ^[1] Para obtener una solución eficiente es necesario especificar varios aspectos del problema:

• Tipos de objetos: Los algoritmos dependen de si S está formado por puntos , rectas , segmentos de recta , cajas , polígonos .... Los objetos más simples y estudiados para buscar son los puntos.
• Tipos de rango: los rangos de consulta también deben extraerse de un conjunto predeterminado. Algunos conjuntos de rangos bien estudiados, y los nombres de los respectivos problemas son rectángulos alineados con ejes (búsqueda de rangos ortogonales), simples , semiespacios y esferas / círculos .
• Tipos de consulta: si se debe informar la lista de todos los objetos que cruzan 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 cruzan el rango. En este caso, el problema se llama conteo de rango y la consulta se llama consulta de conteo . La consulta de vacío informa si hay al menos un objeto que cruza 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 cruzan el rango.
• Búsqueda de rango dinámico versus 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 sin conexión: 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 encerrados en un círculo, una consulta de recuento 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 usó un árbol kd para lograr (en notación Big O ) espacio y tiempo de consulta. ^[2] Bentley también propuso usar árboles de rango , lo que mejoró el tiempo de consulta pero aumentó el espacio . ^[3] Dan Willard utilizó punteros descendentes, un caso especial de cascada fraccionaria para reducir aún más el tiempo de consulta . ^[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 computación Word RAM en dimensiones bajas (2D, 3D, 4D). Bernard Chazelle utilizó árboles de rango comprimido para lograr tiempo y espacio de consulta para el recuento 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 , que también utilizan árboles de rango comprimido en el modelo de cálculo de RAM de palabras, 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 llama 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, entonces 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, se permiten la búsqueda de rango dinámico , las inserciones y eliminaciones de puntos. En la versión incremental del problema, sólo se permiten inserciones, mientras que la versión decremental sólo 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 fraccional dinámica para lograr espacio y tiempo de consulta. ^[8] Tanto la versión incremental como la decremental del problema se pueden resolver con el 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 colores de puntos en el espacio geométrico, entonces se consulta 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 ser considerado en geometría computacional , búsqueda de rangos y búsqueda de rangos ortogonales en particular, tiene aplicaciones para consultas de rangos en bases de datos . La búsqueda por rango de colores también se utiliza y está motivada por la búsqueda a través de datos categóricos. 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 $10 000 y $20 000 podría ser un problema de informes de rango ortogonal donde la edad y el dinero son dos dimensiones.

Ver también

• árbol de rango
• Consulta de rango

Referencias

1. Agarwal, PK ; Erickson, J. (1999), "Búsqueda de rango geométrico y sus parientes", en Chazelle, Bernard ; Buen hombre, Jacob ; Pollack, Richard (eds.), Avances en geometría discreta y computacional: actas de la conferencia de investigación conjunta de verano AMS-IMS-SIAM de 1996, Geometría discreta y computacional: diez años después, 14 al 18 de julio de 1996, Mount Holyoke College , Matemáticas contemporáneas, vol. 223, Prensa de la Sociedad Estadounidense de Matemáticas, págs. 1–56
2. Bentley, Jon (1975). "Árboles de búsqueda binaria multidimensional 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 Computación . 17 (3): 427–462. CiteSeerX 10.1.1.133.9153 . doi :10.1137/0217026. 
6. JaJa, José; Mortensen, cristiano; Shi, Qingmin (2005). "Algoritmos rápidos y eficientes en el espacio para informes y recuento de dominancia multidimensional". Simposio internacional sobre algoritmos y computación : 558–568.
7. Chan, Timoteo ; Larsen, Kasper; Pătrașcu, Mihai (2011). "Búsqueda de rango ortogonal en la RAM, revisada". 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). "Más resultados sobre problemas generalizados de búsqueda de intersecciones: conteo, generación de informes y dinamización". Revista de algoritmos . 19 (2): 282–317. doi :10.1006/jagm.1995.1038. hdl : 11858/00-001M-0000-0014-B721-F .

Otras lecturas

• 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.