La ricerca per intervalli (in inglese range searching) è uno dei problemi geometrici fondamentali della geometria computazionale e delle basi di dati. Data una collezione di oggetti (solitamente punti nello spazio d-dimensionale) e una regione di query (l'intervallo), l'obiettivo è identificare o contare in modo efficiente gli oggetti che si trovano all'interno della regione.
Si distinguono principalmente in due varianti del problema:
Sia un insieme di punti nello spazio euclideo . Data una famiglia di sottoinsiemi di (chiamata spazio delle query), una query di ricerca per intervallo riceve in input un elemento e deve calcolare:
Le forme più comuni per la query sono:
Per superare l'approccio ingenuo di complessità lineare ottenuto scansionando l'intero set di dati, si pre-elaborano i punti costruendo strutture dati specifiche.
Il k-d tree è un albero binario di ricerca in cui ogni nodo non foglia divide lo spazio in due semispazi rispetto a una delle coordinate, alternando ciclicamente le dimensioni ad ogni livello.
Il Range Tree è una struttura dati multilivello orientata ad ottenere tempi di query polilogaritmici, a scapito di una maggiore occupazione di memoria. Un range tree -dimensionale è composto da un albero binario bilanciato sulla prima coordinata, in cui ogni nodo interno punta a un range tree -dimensionale sui punti del suo sottoalbero.
Nella geometria computazionale esiste un bilanciamento intrinseco tra la quantità di memoria utilizzata (spazio di memorizzazione) e la velocità di risposta alla query. La tabella seguente riassume le prestazioni nel caso bidimensionale ():
| Struttura Dati | Spazio di Memoria | Tempo di Query (Reporting) |
|---|---|---|
| K-d Tree | ||
| Range Tree standard | ||
| Range Tree con Fractional Cascading |
Le tecniche di range searching trovano applicazione in molteplici ambiti dell'informatica: