¿Cómo encontrar si un punto está dentro de un conjunto de intervalos?

Question

Busco la manera más rápida para decidir si es o no un punto en una línea se encuentra dentro de un subconjunto de esta línea. me dan un Punto de número entero, y también tengo una "lista" de cualquiera de:

1. Puntos, representado por un número entero (3, 10, 1000, etc)
2. Intervalos, que represento por 2 enteros (2:10 son todos enteros de 2 a 10 inluidos, 50:60, etc.)

En este ejemplo, si el valor de mi punto es 5, entonces devuelvo verdadero porque está incluido en un intervalo , lo mismo para 55. Si mi punto es igual a 1000, también devuelvo verdadero porque coincide con la lista de puntos.

Estoy buscando una forma rápida (más rápida que lineal) para verificar esta condición, SIN tener que exponer tantos enteros como posibles puntos (es decir, para un intervalo 1: 1000 no quiero instanciar 1000 enteros). ¿Se puede hacer esto en un tiempo logarítmico?

Gracias

edición: se puede considerar que cualquier tiempo necesario para pre-procesar la lista de datos es igual a 0, porque una vez que mis intervalos iniciales se procesan Necesito aplicar esta prueba a 10k puntos

Answer 1

Hm, tal vez usted puede utilizar un intervalo o un árbol segmento:

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

Answer 2

Primero verifique un hash_map de puntos. Esa es la simple verificación.

Después, simplemente pedir un mapa de intervalos por la primera coordenada y luego encontrar de límite distinto del punto.

A continuación, compruebe si está contenida en el elemento devuelto. Si no estás en eso, no estás en ninguno.

Answer 3

Si tiene los rangos enteros ordenados y los rangos no coinciden, puede realizar una búsqueda binaria para encontrar el rango correcto en tiempo logarítmico.

¿Hay alguna restricción en el rango? En función de eso, probablemente puedas utilizar la función hashing para buscar en tiempo constante. Pero esto depende de cómo sean tus limitaciones.

Answer 4

Podría hacer eso en tiempo sublineal DANDO una estructura de árbol de datos (recomendaría un B-tree), si no cuenta el tiempo necesario para construir el árbol (la mayoría de los árboles tardan n log o tiempo similar para construir).

Si solo tiene una lista simple, entonces no puede hacerlo mejor que lineal, porque en el peor de los casos tiene que verificar todos los puntos e intervalos.

Answer 5

Se puede utilizar un Bloom Filter para probar un punto y ver si es no en un intervalo, en O (1) tiempo lineal. Si supera esa prueba, debe usar otro método, como una búsqueda binaria, para ver si es definitivamente parte de un intervalo, en el tiempo O (log n).

Answer 6

Después de la reflexión, creo que el siguiente código debe trabajar en tiempo logarítmico, excluyendo el tiempo necesario para construir el mapa:

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; 
} 

Creo que esto debería funcionar, siempre y cuando el mapa se llena correctamente con no -sin intervalos de solapamiento