Download Algoritmos de línea de barrer
Document related concepts
Transcript
Técnicas de diseño de algoritmos Algoritmos de línea de barrer Dra. Elisa Schaeffer [email protected] PISIS / FIME / UANL Lı́nea de barrer– p. 1 Algoritmos de línea de barrer Los algoritmos de lı́nea de barrer (inglés: sweep line o scan line) dividen el problema en partes que se puede procesar en secuencia. Son particularmente comúnes para los problemas de geometrı́a computacional, donde se procesa objetos geométricos como apuntos, líneas, polígonos, etcétera. La instancia del problema está compuesta por la información de la ubicación de los objetos en un espacio definido. Lı́nea de barrer– p. 2 Intuición en plano Para el caso que es espacio sea un plano, se puede imaginar que una línea mueva en el plano, cruzando la parte relevante del espacio donde se ubican los objetos. El movimiento de la línea sigue uno de los ejes u otra línea fija y la línea se para en puntos relevantes al problema. Los puntos de parada se guarda en un montı́culo. La inicialización del montículo y su actualización son asuntos importantes en el diseño del algoritmo. Lı́nea de barrer– p. 3 Información auxiliar También se puede aprovechar de otras estructuras de datos auxiliares, por ejemplo para guardar información sobre cuáles objetos están actualmente bajo de la lı́nea. Entre dos paradas de la línea, los papeles relativos de los objetos pueden cambiar, pero los factores esenciales de la solución del problema no deben cambiar de una parada a otra. Lı́nea de barrer– p. 4 Otras dimensionalidades Si el espacio tiene una sola dimensión, en vez de una línea basta con usar un punto. Para dimensiones mayores n, se “barre” con un hiperplano de dimensión n − 1. Lı́nea de barrer– p. 5 Intersecciones de segmentos Dado: n segmentos de líneas en plano de dos dimensiones Pregunta: ¿Cuáles son los puntos de intersección entre todos los segmentos? Lı́nea de barrer– p. 6 Ejemplo Lı́nea de barrer– p. 7 Algoritmo ingenuo Procesar cada uno de los n(n − 1) = Θ (n2 ) pares de segmentos si ∈ S y sj ∈ S tal que i 6= j y computa su intersección. El el peor caso, esto es el comportamiento óptimo: si todos los segmentos se intersectan, habrá que calcular todas las intersecciones en cualquier caso y solamente imprimir la lista de las instrucciones ya toma Θ (n2 ) tiempo. Lı́nea de barrer– p. 8 Instancias típicas Sin embargo, en una instancia promedia o típica, el número de puntos de intersección k es mucho menor que n(n − 1). El algoritmo mejor imaginable tuviera complejidad asintótica O (n + k), porque se necesita tiempo O (n) para leer la entrada y tiempo O (k) para imprimir la salida. Ahora veremos un algoritmo de línea de barrer que corre en tiempo O ((n + k) log n). Lı́nea de barrer– p. 9 El algoritmo Los puntos de parada serán todos los puntos donde empieza o termina un segmento y además los puntos de intersección. Lı́nea de barrer– p. 10 El algoritmo Los puntos de parada serán todos los puntos donde empieza o termina un segmento y además los puntos de intersección. Son n puntos de comienzo, n puntos finales y k intersecciones. Lı́nea de barrer– p. 10 El algoritmo Los puntos de parada serán todos los puntos donde empieza o termina un segmento y además los puntos de intersección. Son n puntos de comienzo, n puntos finales y k intersecciones. La línea de barrer moverá en perpendicular al x, o sea, en paralelo al eje y. eje Lı́nea de barrer– p. 10 El algoritmo Los puntos de parada serán todos los puntos donde empieza o termina un segmento y además los puntos de intersección. Son n puntos de comienzo, n puntos finales y k intersecciones. La línea de barrer moverá en perpendicular al x, o sea, en paralelo al eje y. eje Se guardará los puntos de parada en un montículo. Lı́nea de barrer– p. 10 El algoritmo Los puntos de parada serán todos los puntos donde empieza o termina un segmento y además los puntos de intersección. Son n puntos de comienzo, n puntos finales y k intersecciones. La línea de barrer moverá en perpendicular al x, o sea, en paralelo al eje y. eje Se guardará los puntos de parada en un montículo. Las actualizaciones necesarias del montículo tomarán O (log n) tiempo cada una. Lı́nea de barrer– p. 10 Observaciones Entre dos puntos de parada, por definición no hay ninguna intersección. El subconjunto de segmentos cuales quedan “bajo” de la línea de barrer, o sea, los segmentos que intersectan con la línea de barrer mientras mueva de un punto de parada al siguiente no cambia. El orden de los puntos de intersección en comparación a cualquier de los dos ejes está fijo. Lı́nea de barrer– p. 11 Ejemplo preprocesado Lı́nea de barrer– p. 12 Estructura de segmentos Guardamos en un árbol binario balanceado los segmentos que quedan actualmente bajo de la línea de barrer. El árbol nos da acceso en tiempo O (log n). Se insertarán según el orden de la coordenada y del punto de intersección del segmento con la línea de barrer. Lı́nea de barrer– p. 13 Actualización del árbol (I) cuando comienza un segmento, se inserta el segmento en el lugar adecuado en el árbol binario (II) cuando termina un segmento, se saca el segmento del árbol, y (III) cuando se intersectan dos segmentos, el segmento que antes estaba arriba se cambia por abajo y viceversa — en este último caso también se imprime el punto de intersección encontrada a la salida Lı́nea de barrer– p. 14 Momento de intersección Por el hecho que el orden está según la coordenada y, a llegar a la intersección de dos segmentos si y sj , son “vecinos” en el árbol por lo menos justo antes de llegar al punto de intersección. Lı́nea de barrer– p. 15 Momento de intersección Por el hecho que el orden está según la coordenada y, a llegar a la intersección de dos segmentos si y sj , son “vecinos” en el árbol por lo menos justo antes de llegar al punto de intersección. Ser vecinos quiere decir que son vértices hoja del árbol que están uno al lado del otro en el nivel bajo. Lı́nea de barrer– p. 15 Momento de intersección Por el hecho que el orden está según la coordenada y, a llegar a la intersección de dos segmentos si y sj , son “vecinos” en el árbol por lo menos justo antes de llegar al punto de intersección. Ser vecinos quiere decir que son vértices hoja del árbol que están uno al lado del otro en el nivel bajo. =⇒ Al haber actualizado la estructura, lo único que tenemos que hacer es calcular las puntos de intersección de los vecinos actuales y añadirles en la cola de puntos de parada. Lı́nea de barrer– p. 15 Momento de intersección Por el hecho que el orden está según la coordenada y, a llegar a la intersección de dos segmentos si y sj , son “vecinos” en el árbol por lo menos justo antes de llegar al punto de intersección. Ser vecinos quiere decir que son vértices hoja del árbol que están uno al lado del otro en el nivel bajo. =⇒ Al haber actualizado la estructura, lo único que tenemos que hacer es calcular las puntos de intersección de los vecinos actuales y añadirles en la cola de puntos de parada. El número máximo de puntos de parada nuevos encontrados al haber hecho una parada es 2. Lı́nea de barrer– p. 15 Pseudocódigo M := un montículo vacío para todo si ∈ S, si = (x1 , y1 ), (x2 , y2 ) tal que x1 ≤ x2 insertar en M el dato [(x1 , y1 ), C, i, −] insertar en M el dato [(x2 , y2 ), F, i, −] B := un árbol binario balanceado vacío mientras M no está vacío (x, y) := el elemento mínimo de M remueve (x, y) de M ... Lı́nea de barrer– p. 16 Pseudocódigo: puntos de inicio si (x, y) es de tipo C como “comienzo” insertar si a B ordenado según la clave y si el vecino izquiero de si en B está definido y está sℓ computar la intersección (x′ , y ′ ) de si y sℓ si x′ > x insertar en M el dato [(x′ , y ′ ), I, ℓ, i] si el vecino derecho de si en B está definido y está sr computar la intersección (x′′ , y ′′ ) de si y sr si x′′ > x insertar en M el dato [(x′′ , y ′′ ), I, i, r] ... Lı́nea de barrer– p. 17 Pseudocódigo: puntos finales si (x, y) es de tipo F como “final” sℓ := el segmento a la izquierda de si en B sr := el segmento a la derecha de si en B remueve si de B si están definidos ambos sℓ y sr , computar la intersección (x′ , y ′ ) de sℓ y sr si x′′ > x insertar en M el dato [(x′ , y ′ ), I, ℓ, r] ... Lı́nea de barrer– p. 18 Pseudocódigo: intersecciones si (x, y) es de tipo “intersección” i := el primer índice definido en el dato j := el segundo índice definido en el dato intercambia las posiciones de si y sj en B si el nuevo vecino izq. de sj en B es sℓ computar la intersección (x′ , y ′ ) de sj y sℓ si x′ > x, insertar en M el dato [(x′ , y ′ ), I, j, ℓ] si el nuevo vecino der. de si en B es sr computar la intersección (x′′ , y ′′ ) de si y sr si x′′ > x, insertar en M el dato [(x′′ , y ′′ ), I, i, r] imprimir (x, y) Lı́nea de barrer– p. 19 Análisis: montículo La construcción al inicio: O (n) Lı́nea de barrer– p. 20 Análisis: montículo La construcción al inicio: O (n) En cada punto preprocesado se realiza una inserción o un retiro de un elemento de un árbol binario balanceado. Lı́nea de barrer– p. 20 Análisis: montículo La construcción al inicio: O (n) En cada punto preprocesado se realiza una inserción o un retiro de un elemento de un árbol binario balanceado. Son en total 2n de tales operaciones. Lı́nea de barrer– p. 20 Análisis: montículo La construcción al inicio: O (n) En cada punto preprocesado se realiza una inserción o un retiro de un elemento de un árbol binario balanceado. Son en total 2n de tales operaciones. Juntas necesitan O (n log n) tiempo. Lı́nea de barrer– p. 20 Análisis: montículo La construcción al inicio: O (n) En cada punto preprocesado se realiza una inserción o un retiro de un elemento de un árbol binario balanceado. Son en total 2n de tales operaciones. Juntas necesitan O (n log n) tiempo. Se añade máx. 2 elementos por cada inserción y al máximo un elemento por cada retiro. Lı́nea de barrer– p. 20 Análisis: montículo La construcción al inicio: O (n) En cada punto preprocesado se realiza una inserción o un retiro de un elemento de un árbol binario balanceado. Son en total 2n de tales operaciones. Juntas necesitan O (n log n) tiempo. Se añade máx. 2 elementos por cada inserción y al máximo un elemento por cada retiro. Cada operación es O (log n) y son O (n) operaciones. Lı́nea de barrer– p. 20 Análisis: intersecciones Hasta ahora todo necesita O (n log n) tiempo. En los puntos de intersección se intercambian posiciones. Lı́nea de barrer– p. 21 Análisis: intersecciones Hasta ahora todo necesita O (n log n) tiempo. En los puntos de intersección se intercambian posiciones. Implementar con dos retiros seguidos por dos inserciones al árbol, de costo O (log n) cada uno. Lı́nea de barrer– p. 21 Análisis: intersecciones Hasta ahora todo necesita O (n log n) tiempo. En los puntos de intersección se intercambian posiciones. Implementar con dos retiros seguidos por dos inserciones al árbol, de costo O (log n) cada uno. Además se inserta al máximo dos puntos al montículo, de costo O (log n) por inserción. Lı́nea de barrer– p. 21 Análisis: intersecciones Hasta ahora todo necesita O (n log n) tiempo. En los puntos de intersección se intercambian posiciones. Implementar con dos retiros seguidos por dos inserciones al árbol, de costo O (log n) cada uno. Además se inserta al máximo dos puntos al montículo, de costo O (log n) por inserción. En total son k intersecciones =⇒ O (k log n). Lı́nea de barrer– p. 21 Análisis: intersecciones Hasta ahora todo necesita O (n log n) tiempo. En los puntos de intersección se intercambian posiciones. Implementar con dos retiros seguidos por dos inserciones al árbol, de costo O (log n) cada uno. Además se inserta al máximo dos puntos al montículo, de costo O (log n) por inserción. En total son k intersecciones =⇒ O (k log n). Tiempo total: O (n log n) + O (k log n) = O ((n + k) log n) Lı́nea de barrer– p. 21 Tarea para entregar el martes Busca en línea un algoritmo de línea de barrer para la construcción de diagramas de Voronoia para un conjunto de puntos en R2 . Da un resumen de las estructuras de datos necesarias y pseudocódigo de nivel general, junto con un análisis de la complejidad. La idea no es tanto copiar directamente el pseudocódigo y el análisis de algún lugar, sino encontrar las definiciones y la idea del algoritmo en línea y después pensar. a Sirven por ejemplo para convertir un conjunto de puntos en un grafo plano — tarea extra es explicar cómo. Lı́nea de barrer– p. 22