En las estructuras de datos , el problema de búsqueda de rango generalmente consiste en preprocesar un conjunto S de objetos para 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, una variante geométrica del problema es encontrar ciudades dentro de un cierto rango de latitud y longitud .
El problema de búsqueda de rango y las estructuras de datos que lo resuelven son un tema fundamental de la geometría computacional . Las aplicaciones del problema surgen en áreas que incluyen sistemas de información geográfica (GIS) y diseño asistido por computadora (CAD) y 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 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 rango: los rangos de consulta también deben extraerse de un conjunto predeterminado. Algunos conjuntos bien estudiados de gamas, y los nombres de los problemas respectivos son rectángulos ejes alineados (ortogonal de búsqueda gama), simplices , semiespacios , y esferas / círculos .
- Tipos de consulta: si se debe informar la lista de todos los objetos que se cruzan con el rango de la consulta, el problema se denomina informe de rango y la consulta se denomina consulta de informe . A veces, solo se requiere el número de objetos que se cruzan con 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 se cruza con 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 reportar la suma del semigrupo de los pesos de los puntos que intersecan el rango.
- Búsqueda de rango dinámico frente a búsqueda de rango estático: En el ajuste estático, 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 todo el conjunto de consultas se conocen de antemano.
Estructuras de datos
Búsqueda de rango ortogonal
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 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 el uso de árboles de distribución , lo que mejoró el tiempo de consulta para pero mayor espacio para . [3] Dan Willard usó punteros descendentes, un caso especial de cascada fraccionada para reducir el tiempo de consulta aún más. [4]
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 de RAM de palabras en dimensiones reducidas (2D, 3D, 4D). Bernard Chazelle utilizó árboles de distribución de compresión para lograr tiempo de consulta y espacio para el recuento de rangos. [5] Joseph JaJa y otros mejoraron posteriormente este tiempo de consulta parapara el recuento de rango, 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 los informes de rango encontrados por Timothy M. Chan , Kasper Larsen y Mihai Pătrașcu , también usando árboles de rango comprimidos en el modelo de cálculo de RAM de palabras, son uno de los siguientes: [7]
- espacio, Tiempo de consulta
- espacio, Tiempo de consulta
- espacio, Tiempo de consulta
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 tiene dos caras y, si ninguno de los límites es infinito, la consulta tiene cuatro caras.
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 búsquedas de rango dinámico , 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 fraccional dinámica para lograr espacio y Tiempo de consulta. [8] Tanto la versión incremental como la decreciente 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.
Búsqueda de rango de colores
El problema del recuento 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 un 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 recuento de rangos de colores ortogonales 2D en espacio y Tiempo de consulta. [9]
Aplicaciones
Además de considerarse en geometría computacional , la búsqueda de rango y la búsqueda de rango ortogonal en particular, tiene aplicaciones para consultas de rango 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 y que tienen entre $ 10000 y $ 20000 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
- ^ Agarwal, PK ; Erickson, J. (1999), "Búsqueda de rango geométrico y sus parientes" (PDF) , en Chazelle, Bernard ; Goodman, Jacob ; Pollack, Richard (eds.), Avances en geometría discreta y computacional: actas de la conferencia conjunta de investigación de verano AMS-IMS-SIAM de 1996, Geometría discreta y computacional - Diez años después, 14-18 de julio de 1996, Mount Holyoke College , Matemáticas contemporáneas, 223 , American Mathematical Society Press, págs. 1-56
- ^ Bentley, Jon (1975). "Árboles de búsqueda binarios multidimensionales utilizados para búsqueda asociativa". Comunicaciones de la ACM . 18 (9): 509–517. doi : 10.1145 / 361002.361007 .
- ^ Bentley, Jon (1980). "Multidimensional divide y vencerás". Comunicaciones de la ACM . 23 (4): 214-229. doi : 10.1145 / 358841.358850 .
- ^ 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 .
- ^ Chazelle, Bernard (1988). "Un enfoque funcional de las estructuras de datos y su uso en búsquedas multidimensionales". Revista SIAM de Computación . 17 (3): 427–462. doi : 10.1137 / 0217026 .
- ^ JaJa, Joseph; Mortensen, Christian; Shi, Qingmin (2005). "Algoritmos rápidos y eficientes en el espacio para informes y conteos de dominancia multidimensional". Simposio internacional sobre algoritmos y computación : 558–568.
- ^ Chan, Timothy ; Larsen, Kasper; Pătrașcu, Mihai (2011). "Búsqueda de rango ortogonal en la RAM, revisada". Simposio sobre geometría computacional : 1-10.
- ^ Mehlhorn, Kurt ; Näher, Stefan (1990). "Cascada fraccionada dinámica". Algoritmica . 5 (2): 215–241. doi : 10.1007 / BF01840386 .
- ^ Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1995). "Más resultados sobre problemas generalizados de búsqueda de intersecciones: recuento, 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, Mark ; Schwarzkopf, Otfried (2000), Computational Geometry (2.a ed.), Berlín: Springer-Verlag, ISBN 3-540-65620-0
- Matoušek, Jiří (1994), "Búsqueda de rango geométrico" , Encuestas de computación de ACM , 26 (4): 421–461, doi : 10.1145 / 197405.197408.