Se nos dan dos conjuntos de segmentos en la línea numérica. ¿Cómo determinaría eficientemente (no en O (| S1 | * | S2 |)) si esos conjuntos se cruzan, es decir, si hay dos segmentos superpuestos, que se encuentran en conjuntos diferentes?

Answer 1

Puede hacerlo en [math] \ mathcal {O} ((| S_1 | + | S_2 |) \ log | S_1 |) [/ math] time.

Primero, clasifique los puntos finales de los segmentos en [math] S_1 [/ math] e itere a través de ellos en orden. A medida que pasa sobre un punto izquierdo para uno de los segmentos, incremente un contador que rastrea el número de segmentos que cubren su ubicación actual. A medida que pasas por un punto correcto, disminuye el contador. Con esto, puede preparar una lista ordenada [matemática] L [/ matemática] de intervalos disjuntos cuya unión es la misma que la de [matemática] S_1 [/ matemática]. Este paso lleva tiempo [math] \ mathcal {O} (| S_1 | \ log | S_1 |) [/ math].

Por ejemplo, si [math] S_1 [/ math] contiene los intervalos [1, 3), [2, 4) y [5, 6), su unión es la misma que la de [math] [1, 4) [/ math] y [math] [5, 6) [/ math]. Puede determinar esto notando que en la coordenada 1, el contador va de 0 (descubierto) a 1 (cubierto); a las 2, va de 1 a 2; a las 3, va de 2 a 1; y luego a las 4, pasa de 1 (cubierto) a 0 (descubierto). Luego, a 5 vuelve a subir a 1, luego a 6 vuelve a bajar a 0.

Una vez que tenga esta lista [matemática] L [/ matemática], puede iterar a través de [matemática] S_2 [/ matemática] y usar [matemática] L [/ matemática] para verificar si cada segmento en [matemática] S_2 [/ matemática] intersecta [matemáticas] S_1 [/ matemáticas]. Para un intervalo dado en [matemática] S_2 [/ matemática], realice una búsqueda binaria para verificar si el punto final izquierdo intersecta uno de los intervalos en [matemática] L [/ matemática]. Si es así, hay una intersección con algún intervalo en [math] S_1 [/ math]. Si no es así, debe estar en uno de los intervalos “vacíos” intermedios, como [4, 5) en el ejemplo anterior. Si el punto final derecho no se encuentra también en el mismo intervalo vacío, eso también significa que hay una intersección con algún intervalo en [matemáticas] S_1 [/ matemáticas].

Answer 2

Ordene ambos conjuntos por el inicio y el secundario por la marca final, sus uniones [matemáticas] O (| S_1 | \ log | S_1 | + | S_2 | \ log | S_2 |) [/ matemáticas]. Ahora averiguar si se cruzan tomará menos que el número mencionado anteriormente. Entonces, si los conjuntos son grandes, esto es más rápido.

Answer 3

Es posible ordenar [math] n [/ math] segmentos (de uno de los conjuntos) en orden en [math] O (n \ log n) [/ math] time. Los segmentos que se superponen pueden fusionarse, reduciendo el tamaño del conjunto. Cuando ambos conjuntos se han ordenado, la comprobación de superposiciones entre ellos es [matemática] O (n_1 + n_2) [/ matemática].