Búsqueda de rango

La búsqueda de rango consiste, en su forma más general, en realizar un preprocesamiento a un conjunto S de objetos con el objetivo de determinar cuáles de estos se intersecan con otro objeto denominado rango. Por ejemplo, S puede ser un conjunto de puntos correspondientes a las coordenadas de varias ciudades, y queremos encontrar aquellas que se encuentran dentro de un determinado rango de longitud y latitud.

Los problemas y estructura de datos de la búsqueda de rango son una temática fundamental de la Geometría computacional. El problema de la búsqueda de rango tiene aplicaciones no solo en áreas relacionadas con el procesamiento de datos geométricos (como sistema de información geográfica o diseño asistido por computadora), sino también en bases de datos.

Variaciones

Este problema presenta diversas variantes y estructuras de datos que pueden ser necesarias para las distintas variantes. Para obtener una solución eficiente, varios aspectos del problema necesitan ser especificados:

• Tipos de objetos: Los algoritmos dependen de si S es un conjunto de puntos, líneas, segmentos, rectángulos, polígonos... Los objetos más simples y estudiados son los puntos.

• Tipos de rangos: Los rangos de cola también necesitan ser dibujados desde un conjunto predeterminado. Algunos conjuntos de rangos bien estudiados y el nombre de los respectivos problemas son: polígonos rectilíneos (búsqueda de rango ortogonal), simplex (búsqueda de rango simples), Semiespacio (búsqueda de rango semiespacial), Esferas / Círculos (búsqueda de rango esférica / búsqueda de rango circular).

• Tipos de consulta: Si se debe reportar la lista de todos los objetos que se intersecan con el rango consultado, el problema se llamaría reporte de rango y la consulta reporte de consulta. En ocasiones, solo hace falta conocer cuántos objetos se encuentran dentro del rango consultado, en este caso el problema se denomina conteo de rango y la consulta consulta de conteo. La consulta vacía informa si hay al menos un objeto que se interseca con el rango pedido. En la versión de semigrupo se especifica un semigrupo conmutativo (S,+), a cada punto en S se le asigna un peso, y se debe informar la suma de semigrupo de los pesos de los puntos que se intersecan con el rango consultado.

• Búsqueda de rango dinámico vs. búsqueda de rango estático: En el caso estático el conjunto S se conoce de antemano. En el dinámico los objetos pueden ser insertados o borrados entre consultas.

• Búsqueda de rango desconectado: Ambos, el conjunto de objetos y todo el conjunto de consultas son conocidas de antemano.

Referencias

• Agarwal, P. K.; Erickson, J. (1999), «Geometric Range Searching and Its Relatives», en Chazelle, Bernard; Goodman, Jacob; Pollack, Richard, eds., Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke College, Contemporary Mathematics 223, American Mathematical Society Press, pp. 1-56, archivado desde el original el 29 de junio de 2011, consultado el 30 de diciembre de 2013 ..
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Computational Geometry (2ª edición), Berlín: Springer-Verlag, ISBN 3-540-65620-0 .. See especially Chapters 5 and 16.
• Matoušek, Jiří (1994), «Geometric range searching», ACM Computing Surveys 26 (4): 421-461 ..