Sección 1: Introducción.

Sección 2: Intersecciones de segmentos.

El primer problema que abordamos es el de detectar las intersecciones de una colección de n segmentos en el plano. Evidentemente, el primer algorimo que se nos puede ocurrir es un algoritmo de fuerza bruta: basta con comprobar si cada par de segmentos en la colección se intersectan o no; así esta algoritmo es cuadrático y en ocasiones es imposible de mejorar puesto que el número de intersecciones que se puede llegar a presentar es cuadrático (si todos los segmentos se intersectan entre si)

 Nos proponemos, a continuación, describir un algoritmo cuya complejidad dependerá del número de intersecciones que presenten los segmentos, puesto que en muchas ocasiones la mayoría de los segmentos no se cortarán entre ellos y así no comprobaremos una posible intersección entre dos segmentos que estén muy alejados entre si. Este tipo de algoritmos son conocidos como output-sensitive puesto que su complejidad depende son sólo del tamaño de la entrada sino también del de la salida. No entraremos aquí en los detalles de la implementación sino que sólo describiremos por encima dicho algoritmo.

Se trata de un algoritmo de barrido. Vamos a barrer el plano por una línea horizontal que irá bajando para detectar todas las intersecciones.  Por lo que deberemos describir los puntos en los que nos dentendremos así como las operaciones que realizaremos en dichos puntos. En principio, nos detendremos en los extremos de los segmentos pero cada vez que detectemos una intersección (y veremos que dicha detección se produce siempre antes de que se produzca) el punto de la intersección nos determinará también un punto de parada. Así tendremos dos tipos de puntos en los que pararnos: los extremos y las intersecciones. La forma de detectar las intersecciones es observando que sólo se puede producir una intersección entre dos segmentos si estos segmentos son consecutivos en algún momento en el barrido inmediatamente anterior a que se produzca la intersección.  Así en cada momento mantendremos la listas ordenada de los segmentos que estamos atravesando. Esto determina que en realidad tenemos tres tipos de puntos: los extremos superiores, los extremos inferiores y las intersecciones. las operaciones por tanto son:

• Si estamos en un extremo superior: añadir el segmento en el lugar adecuado y comprobar su intersección con el anterior y posterior.
• Si estamos en un extremo inferior: eliminar el segmento adecuado y comprobar la intersección entre su anterior y su posterior (que ahora son contiguos).
• Si estamos ante una intersección cambiar el orden de los segmentos y comprobar la intersección de cada uno de ellos con su contiguo.

Obsérvese que el algoritmo anterior es peor que el de fuerza bruta en el caso de que el número de intersecciones sea muy alto pero mejor en el caso de que el número de intersecciones sea lineal.
 
 

Sección 3: Intersección de semiplanos

Así supongamos que tenemos n semiplanos H={h_i: i=1, ..., n}  y queremos calcular su intersección, ello es posible con un algoritmo de divide y vencerás: dividimos H en dos subconjuntos H₁ y H₂ de aproximadamente el mismo tamaño y calculamos recursivamente la intersección de dichos subconjuntos de semiplanos obteniéndose dos regiones convexas C₁ y C₂, ahora bastará con calcular la intersección de dichas regiones para obtener la intersección de los elementos de H, veamos como podemos realizar dicha operación.

Así tenemos dos regiones convexas delimitadas por segmentos o por semirectas y queremos calcular su intersección. Dicho cálculo lo realizaremos mediante un algoritmo de barrido similar, en algún sentido al descrito para la intersección de segmentos pero que aprovechará la especial estructura de la que disponemos. Así, no será necesario considerar como puntos de paradas las intersecciones, ni ordenar previamente los puntos (puestos que estos ya están ordenados) y en cada línea horizontal a lo más corta a cuatro segmentos, con lo cual la actualización se realizará en tiempo constante y no logarítmico, con lo cual tenemos:

Teorema 6.2: Es posible calcular la intersección de dos regiones convexas limitadas por n segmentos o semirectas en tiempo lineal.

Corolario 6.1: Es posible calcular la intersección de n semiplanos en tiempo O(n log n).

Demostración: Para calcular la intersección de los n semiplanos, basta con aplicar un algoritmo de divide y vencerás, donde la unión se realiza aplicando el Teorema 6.2, por tanto se tiene que T(N) = 2T(N/2)+ O(N) lo que da lugar a la complejidad expresada.
 

Ejercicios

1. Dar un algoritmo que compute las I intersecciones de n circunferencias en el plano en tiempo O(n log n + I log n).
2. Dar un algoritmo que calcule las intersecciones entre n segmentos horizontales y m segmentos verticales.
3. Sea H una colección de más de tres semiplanos. Un semiplano h de H se dice redundante si no contribuye con ninguna arista a la intersección de H. Probar que por cada h redundante, existen h' y h'' en H, tal que h contiene a la intersección de h' con h''.