Algoritmo de Bentley-Ottmann

En geometría computacional , el algoritmo de Bentley-Ottmann es un algoritmo de barrido lineal para enumerar todos los cruces en un conjunto de segmentos de línea , es decir, encuentra los puntos de intersección (o, simplemente, intersecciones ) de los segmentos de línea. Extiende el algoritmo de Shamos-Hoey , ^{[ 1 ]} un algoritmo anterior similar para comprobar si un conjunto de segmentos de línea tiene o no algún cruce. Para una entrada que consiste en${\displaystyle n}$segmentos de línea con${\displaystyle k}$En los cruces (o intersecciones), el algoritmo de Bentley-Ottmann requiere tiempo.${\displaystyle {\mathcal {O}}((n+k)\log n)}$. En los casos en que${\displaystyle k={\mathcal {o}}\left({\frac {n^{2}}{\log n}}\right)}$Esto supone una mejora respecto a un algoritmo ingenuo que prueba cada par de segmentos, lo que lleva${\displaystyle \Theta (n^{2})}$.

El algoritmo fue desarrollado inicialmente por Jon Bentley y Thomas Ottmann ( 1979 ) ; se describe con más detalle en los libros de texto Preparata y Shamos (1985) , O'Rourke (1998) y de Berg et al. (2000) . Aunque Chazelle y Edelsbrunner (1992) y Balaban (1995) conocen ahora algoritmos asintóticamente más rápidos , el algoritmo de Bentley-Ottmann sigue siendo una opción práctica debido a su simplicidad y bajos requisitos de memoria . 

La idea principal del algoritmo de Bentley-Ottmann es utilizar un enfoque de línea de barrido , en el que una línea vertical L se mueve de izquierda a derecha (o, por ejemplo, de arriba a abajo) a través del plano, intersectando los segmentos de línea de entrada en secuencia a medida que se mueve. ^{[ 2 ]} El algoritmo se describe más fácilmente en su posición general , lo que significa:

1. Ningún par de extremos o intersecciones de segmentos de línea tienen la misma coordenada x.
2. Ningún extremo de un segmento de línea se encuentra sobre otro segmento de línea.
3. Ningún par de segmentos de línea se cruza en un solo punto.

En tal caso, L siempre intersecará los segmentos de línea de entrada en un conjunto de puntos cuyo orden vertical cambia únicamente en un conjunto finito de eventos discretos . Específicamente, un evento discreto puede asociarse con un extremo (izquierdo o derecho) de un segmento de línea o con el punto de intersección de dos segmentos de línea. Por lo tanto, el movimiento continuo de L puede descomponerse en una secuencia finita de pasos y simularse mediante un algoritmo que se ejecuta en un tiempo finito.

Existen dos tipos de eventos que pueden ocurrir durante esta simulación. Cuando L recorre un extremo de un segmento de línea s , la intersección de L con s se agrega o se elimina del conjunto de puntos de intersección ordenados verticalmente. Estos eventos son fáciles de predecir, ya que los extremos se conocen a partir de la entrada del algoritmo. Los eventos restantes ocurren cuando L recorre un cruce (o intersección) entre dos segmentos de línea s y t . Estos eventos también pueden predecirse a partir del hecho de que, justo antes del evento, los puntos de intersección de L con s y t son adyacentes en el orden vertical de los puntos de intersección .

El algoritmo de Bentley-Ottmann mantiene estructuras de datos que representan el orden vertical actual de los puntos de intersección de la línea de barrido con los segmentos de línea de entrada, así como un conjunto de posibles eventos futuros formados por pares adyacentes de puntos de intersección. Procesa cada evento a su vez, actualizando sus estructuras de datos para representar el nuevo conjunto de puntos de intersección.

Para mantener de manera eficiente los puntos de intersección de la línea de barrido L con los segmentos de línea de entrada y la secuencia de eventos futuros, el algoritmo de Bentley-Ottmann mantiene dos estructuras de datos :

• Un árbol de búsqueda binaria (el "árbol de estado de la línea de barrido"), que contiene el conjunto de segmentos de línea de entrada que cruzan L , ordenados por las coordenadas y de los puntos donde estos segmentos cruzan L. Los puntos de cruce en sí no están representados explícitamente en el árbol de búsqueda binaria. El algoritmo de Bentley-Ottmann insertará un nuevo segmento s en esta estructura de datos cuando la línea de barrido L cruce el punto final izquierdo p de este segmento (es decir, el punto final del segmento con la coordenada x más pequeña , siempre que la línea de barrido L comience desde la izquierda, como se explicó anteriormente en este artículo). La posición correcta del segmento s en el árbol de búsqueda binaria puede determinarse mediante una búsqueda binaria, cada paso de la cual comprueba si p está por encima o por debajo de algún otro segmento que es cruzado por L. Por lo tanto, una inserción puede realizarse en tiempo logarítmico. El algoritmo de Bentley-Ottmann también eliminará segmentos del árbol de búsqueda binaria y utilizará el árbol de búsqueda binaria para determinar los segmentos que están inmediatamente por encima o por debajo de otros segmentos; Estas operaciones pueden realizarse utilizando únicamente la estructura del árbol, sin hacer referencia a la geometría subyacente de los segmentos.

• Una cola de prioridad (la "cola de eventos") se utiliza para mantener una secuencia de posibles eventos futuros en el algoritmo de Bentley-Ottmann. Cada evento se asocia con un punto p en el plano, ya sea el extremo de un segmento o un punto de intersección, y ocurre cuando la línea L pasa por p . Por lo tanto, los eventos se pueden priorizar según las coordenadas x de los puntos asociados a cada evento. En el algoritmo de Bentley-Ottmann, los posibles eventos futuros consisten en los extremos de los segmentos de línea que aún no han pasado por el algoritmo y los puntos de intersección de pares de líneas que contienen pares de segmentos que se encuentran inmediatamente uno encima del otro o uno debajo del otro.

El algoritmo no necesita mantener explícitamente una representación de la línea de barrido L ni de su posición en el plano. En cambio, la posición de L se representa indirectamente: es la línea vertical que pasa por el punto asociado al evento procesado más recientemente.

El árbol de búsqueda binaria puede ser cualquier estructura de datos de árbol de búsqueda binaria balanceada , como un árbol rojo-negro ; lo único que se requiere es que las inserciones, eliminaciones y búsquedas tengan una complejidad logarítmica. De manera similar, la cola de prioridad puede ser un montículo binario o cualquier otra cola de prioridad con complejidad logarítmica; no son necesarias colas de prioridad más sofisticadas, como un montículo de Fibonacci . Cabe destacar que la complejidad espacial de la cola de prioridad depende de la estructura de datos utilizada para su implementación.

El algoritmo de Bentley-Ottmann realiza los siguientes pasos.

1. Inicializa una cola de prioridad Q con posibles eventos futuros, cada uno asociado a un punto en el plano y priorizado según la coordenada x de dicho punto. Así, inicialmente, Q contiene un evento para cada uno de los extremos de los segmentos de entrada.
2. Inicializa un árbol de búsqueda binaria autoequilibrado T con los segmentos de línea que cruzan la línea de barrido L , ordenados según las coordenadas y de los puntos de cruce. Inicialmente, T está vacío. (Aunque la línea de barrido L no se representa explícitamente, puede ser útil imaginarla como una línea vertical que, inicialmente, se encuentra a la izquierda de todos los segmentos de entrada).
3. Mientras Q no esté vacío, encuentre y elimine de Q el evento asociado con un punto p con la coordenada x mínima . Determine qué tipo de evento es y procéselo de acuerdo con el siguiente análisis de caso:
   • Si p es el extremo izquierdo de un segmento de línea s , inserta s en T. Encuentra los segmentos de línea r y t que están respectivamente inmediatamente encima y debajo de s en T (si existen); si el cruce de r y t (vecinos de s en la estructura de datos de estado) forma un posible evento futuro en la cola de eventos, elimina este posible evento futuro de la cola de eventos. Si s cruza r o t , agrega esos puntos de cruce como posibles eventos futuros en la cola de eventos.
   • Si p es el extremo derecho de un segmento de línea s , elimina s de T. Encuentra los segmentos r y t que (antes de eliminar s ) estaban respectivamente inmediatamente encima y debajo de él en T (si existen). Si r y t se cruzan, agrega ese punto de cruce como un posible evento futuro en la cola de eventos.
   • Si p es el punto de intersección de dos segmentos s y t (con s debajo de t a la izquierda de la intersección), intercambie las posiciones de s y t en T. Después del intercambio, encuentre los segmentos r y u (si existen) que están inmediatamente debajo y encima de t y s , respectivamente. Elimine cualquier punto de intersección rs (es decir, un punto de intersección entre r y s ) y tu (es decir, un punto de intersección entre t y u ) de la cola de eventos y, si r y t se cruzan o s y u se cruzan, agregue esos puntos de intersección a la cola de eventos.

El algoritmo procesa un evento por punto final de segmento o punto de cruce, en el orden ordenado de los${\displaystyle x}$-coordenadas de estos puntos, como se puede demostrar por inducción. Esto se deduce porque, una vez que${\displaystyle i}$El evento ha sido procesado, el siguiente evento (si es un punto de cruce) debe ser un cruce de dos segmentos que son adyacentes en el orden de los segmentos representados por${\displaystyle T}$Y dado que el algoritmo mantiene todos los cruces entre segmentos adyacentes como posibles eventos futuros en la cola de eventos, el siguiente evento correcto siempre estará presente en dicha cola. En consecuencia, encuentra correctamente todos los cruces de los segmentos de línea de entrada, el problema para el que fue diseñado.

El algoritmo de Bentley-Ottmann procesa una secuencia de${\displaystyle 2n+k}$eventos, donde${\displaystyle n}$denota el número de segmentos de línea de entrada y${\displaystyle k}$denota el número de cruces. Cada evento es procesado por un número constante de operaciones en el árbol de búsqueda binaria y la cola de eventos, y (debido a que contiene solo puntos finales de segmento y cruces entre segmentos adyacentes) la cola de eventos nunca contiene más de${\displaystyle 3n}$eventos. Todas las operaciones requieren tiempo.${\displaystyle {\mathcal {O}}(\log n)}$Por lo tanto, el tiempo total para el algoritmo es${\displaystyle {\mathcal {O}}((n+k)\log n)}$.

Si los cruces encontrados por el algoritmo no necesitan almacenarse una vez encontrados, el espacio utilizado por el algoritmo en cualquier momento es${\displaystyle {\mathcal {O}}(n)}$: cada uno de los${\displaystyle n}$Los segmentos de línea de entrada corresponden a como máximo un nodo del árbol de búsqueda binaria T , y como se indicó anteriormente, la cola de eventos contiene como máximo${\displaystyle 3n}$elementos. Este límite de espacio se debe a Brown (1981) ; la versión original del algoritmo era ligeramente diferente (no eliminaba los eventos de cruce de${\displaystyle Q}$cuando algún otro evento hace que los dos segmentos que se cruzan dejen de ser adyacentes) haciendo que utilice más espacio. ^{[ 3 ]}

Chen y Chan (2003) describieron una versión altamente eficiente en espacio del algoritmo de Bentley-Ottmann que codifica la mayor parte de su información en el ordenamiento de los segmentos en una matriz que representa la entrada, requiriendo solo${\displaystyle {\mathcal {O}}(\log ^{2}n)}$celdas de memoria adicionales. Sin embargo, para acceder a la información codificada, el algoritmo se ralentiza por un factor logarítmico.

La descripción del algoritmo anterior asume que los segmentos de línea no son verticales, que los extremos de los segmentos de línea no se encuentran sobre otros segmentos de línea, que los cruces están formados por solo dos segmentos de línea y que no hay dos puntos de evento con la misma coordenada x . En otras palabras, no toma en cuenta los casos límite, es decir, asume la posición general de los extremos de los segmentos de entrada. Sin embargo, estas suposiciones de posición general no son razonables para la mayoría de las aplicaciones de intersección de segmentos de línea. Bentley y Ottmann (1979) sugirieron perturbar ligeramente la entrada para evitar este tipo de coincidencias numéricas, pero no describieron en detalle cómo realizar estas perturbaciones. De Berg et al. (2000) describen con más detalle las siguientes medidas para manejar entradas de posición especial:

• Se resuelven los empates entre puntos de evento con la misma coordenada x utilizando la coordenada y . Los eventos con diferentes coordenadas y se manejan como antes. Esta modificación resuelve tanto el problema de múltiples puntos de evento con la misma coordenada x como el de los segmentos de línea verticales: el extremo izquierdo de un segmento vertical se define como aquel con la menor coordenada y , y los pasos necesarios para procesar dicho segmento son esencialmente los mismos que los necesarios para procesar un segmento no vertical con una pendiente muy pronunciada.
• Un segmento de línea se define como un conjunto cerrado que contiene sus extremos. Por lo tanto, dos segmentos de línea que comparten un extremo, o un segmento de línea que contiene el extremo de otro segmento, se consideran la intersección de dos segmentos de línea.
• Cuando varios segmentos de línea se intersecan en un mismo punto, se crea y procesa un único punto de evento para dicha intersección. Las actualizaciones del árbol de búsqueda binaria provocadas por este evento pueden incluir la eliminación de cualquier segmento de línea cuyo extremo derecho coincida con este punto, la inserción de nuevos segmentos de línea cuyo extremo izquierdo coincida con este punto y la inversión del orden de los segmentos restantes que contienen dicho punto de evento. El resultado de la versión del algoritmo descrita por de Berg et al. (2000) consiste en el conjunto de puntos de intersección de los segmentos de línea, etiquetados según los segmentos a los que pertenecen, en lugar del conjunto de pares de segmentos de línea que se intersecan.

Se utilizó un enfoque similar para las degeneraciones en la implementación LEDA del algoritmo de Bentley-Ottmann. ^{[ 4 ]}

Para la corrección del algoritmo, es necesario determinar sin aproximaciones las relaciones arriba-abajo entre el punto final de un segmento de línea y otros segmentos de línea, y priorizar correctamente los diferentes puntos de evento. Por esta razón, es estándar usar coordenadas enteras para los puntos finales de los segmentos de línea de entrada, y representar las coordenadas de números racionales de los puntos de intersección de dos segmentos de forma exacta, usando aritmética de precisión arbitraria . Sin embargo, puede ser posible acelerar los cálculos y comparaciones de estas coordenadas usando cálculos de punto flotante y probando si los valores calculados de esta manera están suficientemente lejos de cero como para que puedan usarse sin ninguna posibilidad de error. ^{[ 4 ]} Los cálculos aritméticos exactos requeridos por una implementación ingenua del algoritmo de Bentley-Ottmann pueden requerir cinco veces más bits de precisión que las coordenadas de entrada, pero Boissonat y Preparata (2000) describen modificaciones al algoritmo que reducen la cantidad necesaria de precisión al doble del número de bits que las coordenadas de entrada.

La parte O( n log n ) del límite de tiempo para el algoritmo de Bentley-Ottmann es necesaria, ya que existen límites inferiores coincidentes para el problema de detectar segmentos de línea que se intersecan en modelos de árbol de decisión algebraicos de computación. ^{[ 5 ]} Sin embargo, la dependencia de k , el número de cruces, puede mejorarse. Clarkson (1988) y Mulmuley (1988) proporcionaron algoritmos aleatorios para construir el grafo planar cuyos vértices son puntos finales y cruces de segmentos de línea, y cuyas aristas son las porciones de los segmentos que conectan estos vértices, en un tiempo esperado O( n log n + k ), y este problema de construcción de arreglos fue resuelto determinísticamente en el mismo límite de tiempo O( n log n + k ) por Chazelle y Edelsbrunner (1992) . Sin embargo, construir este arreglo en su conjunto requiere un espacio O( n + k ), mayor que el límite de espacio O( n ) del algoritmo de Bentley-Ottmann; Balaban (1995) describió un algoritmo diferente que enumera todas las intersecciones en un tiempo O( n log n + k ) y un espacio O( n ).

Si los segmentos de línea de entrada y sus puntos finales forman las aristas y los vértices de un grafo conectado (posiblemente con cruces), la parte O( n log n ) del límite de tiempo para el algoritmo de Bentley-Ottmann también puede reducirse. Como muestran Clarkson, Cole y Tarjan (1992) , en este caso hay un algoritmo aleatorio para resolver el problema en un tiempo esperado O( n log* n + k ), donde log * denota el logaritmo iterado , una función que crece mucho más lentamente que el logaritmo. Un algoritmo aleatorio estrechamente relacionado de Eppstein, Goodrich y Strash (2009) resuelve el mismo problema en un tiempo O( n + k log ^{( i )} n ) para cualquier constante i , donde log ^{( i )} denota la función obtenida al iterar la función logaritmo i veces. El primero de estos algoritmos tiene un tiempo lineal siempre que k sea mayor que n por un factor log ^{( i )} n , para cualquier constante i , mientras que el segundo algoritmo tiene un tiempo lineal siempre que k sea menor que n por un factor log ^{( i )} n . Ambos algoritmos implican la aplicación del algoritmo de Bentley-Ottmann a pequeñas muestras aleatorias de la entrada.

• Balaban, IJ (1995), "Un algoritmo óptimo para encontrar intersecciones de segmentos", Actas del 11.º Simposio ACM sobre Geometría Computacional , págs. 211–219 , doi : 10.1145/220279.220302 , ISBN  0-89791-724-3, S2CID 6342118 .
• Bartuschka, U.; Mehlhorn, K .; Näher, S. (1997), "Una implementación robusta y eficiente de un algoritmo de línea de barrido para el problema de intersección de segmentos de línea recta" , en Italiano, GF ; Orlando, S. (eds.), Proc. Worksh. Algorithm Engineering , archivado del original el 6 de junio de 2017 , recuperado el 27 de mayo de 2009..
• Bentley, JL ; Ottmann, TA (1979), "Algoritmos para informar y contar intersecciones geométricas", IEEE Transactions on Computers , C-28 (9): 643–647 , doi : 10.1109/TC.1979.1675432 , S2CID 1618521 .
• de Berg, Mark; van Kreveld, Marc; Overmars, Marcos ; Schwarzkopf, Otfried (2000), "Capítulo 2: Intersección de segmentos de línea" , Geometría computacional (2ª  ed.), Springer-Verlag, págs. 19–44 , ISBN  978-3-540-65620-3.
• Boissonat, J.-D.; Preparata, FP (2000), "Barrido plano robusto para segmentos que se intersecan" (PDF) , SIAM Journal on Computing , 29 (5): 1401– 1421, doi : 10.1137/S0097539797329373.
• Brown, KQ (1981), "Comentarios sobre "Algoritmos para informar y contar intersecciones geométricas"IEEE Transactions on Computers , C-30 (2): 147, doi : 10.1109/tc.1981.6312179 , S2CID 206622367 .
• Chazelle, Bernard ; Edelsbrunner, Herbert (1992), "Un algoritmo óptimo para la intersección de segmentos de línea en el plano", Journal of the ACM , 39 (1): 1– 54, doi : 10.1145/147508.147511 , S2CID 785741 .
• Chen, EY; Chan, TM (2003), "Un algoritmo eficiente en espacio para la intersección de segmentos", Actas de la 15.ª Conferencia Canadiense sobre Geometría Computacional (PDF).
• Clarkson, KL (1988), "Aplicaciones del muestreo aleatorio en geometría computacional, II", Actas del 4.º Simposio ACM sobre Geometría Computacional , págs. 1-11 , doi : 10.1145/73393.73394 , ISBN  0-89791-270-5, S2CID 15134654 .
• Clarkson, KL ; Cole, R.; Tarjan, RE (1992), "Algoritmos paralelos aleatorios para diagramas trapezoidales", International Journal of Computational Geometry and Applications , 2 (2): 117– 133, doi : 10.1142/S0218195992000081. Corrección, 2 (3): 341–343.
• Eppstein, D.; Goodrich , M .; Strash, D. (2009), "Algoritmos de tiempo lineal para grafos geométricos con un número sublineal de cruces", Actas del 20.º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA 2009) , págs. 150–159 , arXiv : 0812.0893 , Bibcode : 2008arXiv0812.0893E , doi : 10.1137/090759112 , S2CID 13044724  .
• Mulmuley, K. (1988), "Un algoritmo rápido de partición planar, I", Actas del 29.º Simposio IEEE sobre Fundamentos de la Informática (FOCS 1988) , págs. 580–589 , doi : 10.1109/SFCS.1988.21974 , ISBN  0-8186-0877-3, S2CID 34582594 .
• O'Rourke, J. (1998), "Sección 7.7: Intersección de segmentos", Geometría computacional en C (2.ª  ed.), Cambridge University Press, pp. 263–265 , ISBN  978-0-521-64976-6.
• Preparata, FP ; Shamos, MI (1985), "Sección 7.2.3: Intersección de segmentos de línea", Geometría computacional: una introducción , Springer-Verlag, págs. 278–287 , Bibcode : 1985cgai.book.....P .
• Pach, J.; Sharir , M. (1991), "Sobre la visibilidad vertical en arreglos de segmentos y el tamaño de la cola en el algoritmo de barrido de línea de Bentley-Ottmann", SIAM Journal on Computing , 20 (3): 460–470 , doi : 10.1137/0220029 , MR 1094525 .
• Shamos, MI ; Hoey, Dan (1976), "Problemas de intersección geométrica", 17.ª Conferencia IEEE sobre Fundamentos de la Informática (FOCS 1976) , págs. 208–215 , doi : 10.1109/SFCS.1976.16 , S2CID 124804  .

• Smid, Michiel (2003), Cálculo de intersecciones en un conjunto de segmentos de línea: el algoritmo de Bentley-Ottmann (PDF).