Come trovare se un punto si trova all'interno di un set di intervalli?

Question

Sto cercando il modo più veloce per decidere se un punto su una linea è o meno all'interno di un sottoinsieme di questa linea. mi viene data un punto intero, e ho anche una "lista" di entrambi:

1. Punti, rappresentata da un numero intero (3, 10, 1000, ecc)
2. intervalli, che rappresento da 2 interi (2:10 è tutti i numeri interi da 2 a 10 inclusi.Possono, 50:60, ecc)

in questo esempio, se il valore del mio punto è 5, allora torno vero perché è incluso in un intervallo , lo stesso per 55. Se il mio punto è uguale a 1000, restituisco anche true perché corrisponde all'elenco di punti.

Sto cercando un modo veloce (più veloce di lineare) per verificare questa condizione, SENZA dover instanciare il numero intero come molti punti possibili (ad esempio, per un intervallo di 1: 1000 non desidero instanciare 1000 interi). Questo può essere fatto in un tempo logaritmico?

Grazie

edit: si può considerare che qualsiasi tempo necessario per pre-processo l'elenco dei dati è uguale a 0, perché una volta che i miei intervalli iniziali vengono elaborati ho bisogno di applicare questo test per 10k punti

Answer 1

Hm, forse è possibile utilizzare un intervallo o un albero segmento:

• http://en.wikipedia.org/wiki/Segment_tree
• http://en.wikipedia.org/wiki/Interval_tree

Answer 2

Prima verifica una hash_map di punti. Questo è il semplice controllo.

Quindi, basta ordinare una mappa di intervalli dalla prima coordinata e quindi trovare il limite inferiore del punto.

Quindi controllare se si è contenuti nell'elemento restituito. Se non ci sei, non ci sei.

Answer 3

Se gli intervalli di numeri interi sono ordinati e gli intervalli non si sovrappongono, è possibile eseguire la ricerca binaria per trovare l'intervallo corretto in tempo logaritmico.

Ci sono dei limiti sull'intervallo? In base a ciò, è probabile che tu possa trovare una funzione di hashing per la ricerca in un tempo costante. Ma questo dipende da come sono i tuoi vincoli.

Answer 4

Si potrebbe fare in tempo sublimatico DATO una struttura dati dell'albero (mi raccomando un albero B), se non si conta il tempo impiegato per costruire l'albero (la maggior parte degli alberi prende n log n o tempo simile costruire).

Se si dispone solo di un elenco semplice, non si può fare meglio di lineare perché nel caso peggiore è necessario controllare tutti i punti e gli intervalli.

Answer 5

è possibile utilizzare un Bloom Filter per testare un punto e vedere se è non in un intervallo, in tempo lineare O (1). Se supera quel test, devi utilizzare un altro metodo come una ricerca binaria per vedere se è definitivamente parte di un intervallo, in O (log n) tempo.

Answer 6

Dopo riflessione, penso che il seguente codice dovrebbe funzionare in tempo logaritmico, escluso il tempo necessario per costruire la mappa:

enum pointType { 
    point, 
    open, 
    close 
}; 
std::map<long int, pointType> mapPoints; 

mapPoints.insert(std::pair<long int, pointType>(3, point)); 

//create the 5:10 interval: 
mapPoints.insert(std::pair<long int, pointType>(5, open)); 
mapPoints.insert(std::pair<long int, pointType>(10, close)); 

int number = 4; 
bool inside = false; 
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number); 

if(it1->first == number || it1->second == close) { 
    inside = true; 
} 

Penso che questo dovrebbe funzionare fino a quando la mappa è riempito correttamente con non - intervalli di sovrapposizione