Algoritmo de línea de barrido

En geometría computacional , un algoritmo de barrido lineal o de barrido plano es un paradigma algorítmico que utiliza una línea o superficie de barrido conceptual para resolver diversos problemas en el espacio euclidiano . Es una de las técnicas fundamentales en geometría computacional.

La idea detrás de los algoritmos de este tipo es imaginar que una línea (a menudo vertical) se desplaza por el plano, deteniéndose en ciertos puntos. Las operaciones geométricas se limitan a los objetos geométricos que se intersecan o se encuentran en las inmediaciones de la línea de desplazamiento cuando esta se detiene, y la solución completa está disponible una vez que la línea ha pasado por todos los objetos.

Una aplicación de este enfoque condujo a un avance significativo en la complejidad computacional de los algoritmos geométricos cuando Shamos y Hoey presentaron algoritmos para la intersección de segmentos de línea en el plano en 1976. En particular, describieron cómo una combinación del enfoque de línea de exploración con estructuras de datos eficientes ( árboles de búsqueda binaria autoequilibrados ) permite detectar si existen intersecciones entre N segmentos en el plano con una complejidad temporal de O ( N log N ) . ^{[ 1 ]} El algoritmo de Bentley-Ottmann, estrechamente relacionado , utiliza una técnica de línea de barrido para reportar todas las K intersecciones entre cualquier N segmentos en el plano con una complejidad temporal de O(( N + K ) log N ) y una complejidad espacial de O( N ) . ^{[ 2 ]}

Desde entonces, este enfoque se ha utilizado para diseñar algoritmos eficientes para una serie de problemas en geometría computacional, como la construcción del diagrama de Voronoi ( algoritmo de Fortune ) y la triangulación de Delaunay o las operaciones booleanas en polígonos .

El barrido topológico es una forma de barrido plano con un ordenamiento simple de los puntos de procesamiento, lo que evita la necesidad de ordenar completamente los puntos; permite que algunos algoritmos de barrido lineal se realicen de manera más eficiente.

La técnica de calibradores giratorios para el diseño de algoritmos geométricos también puede interpretarse como una forma de barrido de plano, en el dual proyectivo del plano de entrada: una forma de dualidad proyectiva transforma la pendiente de una línea en un plano en la coordenada x de un punto en el plano dual, de modo que la progresión a través de líneas ordenadas por su pendiente, tal como la realiza un algoritmo de calibradores giratorios, es dual a la progresión a través de puntos ordenados por sus coordenadas x en un algoritmo de barrido de plano. ^{[ 3 ]}

El enfoque de barrido puede generalizarse a dimensiones superiores. ^{[ 4 ]}