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.

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.

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: