stringtranslate.com

Algoritmo de Bentley-Ottmann

En geometría computacional , el algoritmo de Bentley-Ottmann es un algoritmo de línea de barrido 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 similar anterior para probar si un conjunto de segmentos de línea tiene o no cruces. Para una entrada que consiste en segmentos de línea con cruces (o intersecciones), el algoritmo de Bentley-Ottmann toma tiempo . En los casos en que , esto es una mejora de un algoritmo ingenuo que prueba cada par de segmentos, que toma .

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

Estrategia general

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 , es decir:

  1. No hay dos puntos finales o cruces de segmentos de línea que tengan la misma coordenada x
  2. Ningún extremo de un segmento de línea se encuentra sobre otro segmento de línea.
  3. No hay tres segmentos de línea que se crucen en un solo punto.

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

Hay dos tipos de eventos que pueden ocurrir durante el curso de esta simulación. Cuando L barre a través de un punto final de un segmento de línea s , la intersección de L con s se agrega o elimina del conjunto ordenado verticalmente de puntos de intersección. Estos eventos son fáciles de predecir, ya que los puntos finales ya se conocen a partir de la entrada al algoritmo. Los eventos restantes ocurren cuando L barre a través de un cruce entre (o intersección de) dos segmentos de línea s y t . Estos eventos también se pueden predecir 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 [ aclaración necesaria ] .

El algoritmo de Bentley-Ottmann mantiene estructuras de datos que representan el ordenamiento vertical actual de los puntos de intersección de la línea de barrido con los segmentos de línea de entrada, y una colección de posibles eventos futuros formados por pares adyacentes de puntos de intersección. Procesa cada evento por turno, actualizando sus estructuras de datos para representar el nuevo conjunto de puntos de intersección.

Estructuras de datos

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 Bentley-Ottmann mantiene dos estructuras de datos :

El algoritmo no necesita mantener explícitamente una representación de la línea de barrido L o 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 con el evento procesado más recientemente.

El árbol binario de búsqueda puede ser cualquier estructura de datos de árbol binario de búsqueda balanceada , como un árbol rojo-negro ; todo lo que se requiere es que las inserciones, eliminaciones y búsquedas tomen un tiempo logarítmico. De manera similar, la cola de prioridad puede ser un montón binario o cualquier otra cola de prioridad de tiempo logarítmico; no son necesarias colas de prioridad más sofisticadas, como un montón de Fibonacci . Tenga en cuenta que la complejidad espacial de la cola de prioridad depende de la estructura de datos utilizada para implementarla.

Algoritmo detallado

El algoritmo Bentley-Ottmann realiza los siguientes pasos.

  1. Inicialice una cola de prioridad Q de posibles eventos futuros, cada uno asociado con un punto en el plano y priorizado por la coordenada x del punto. Por lo tanto, inicialmente, Q contiene un evento para cada uno de los puntos finales de los segmentos de entrada.
  2. Inicialice un árbol binario de búsqueda autoequilibrado T de los segmentos de línea que cruzan la línea de barrido L , ordenados por las coordenadas y de los puntos de cruce. Inicialmente, T está vacío. (Aunque la línea de barrido L no está representada explícitamente, puede ser útil imaginarla como una línea vertical que, inicialmente, está a la izquierda de todos los segmentos de entrada).
  3. Mientras Q no esté vacío, busque y elimine el evento de Q asociado con un punto p con la coordenada x mínima . Determine de qué tipo de evento se trata y procese según el siguiente análisis de caso:
    • Si p es el extremo izquierdo de un segmento de línea s , inserte s en T . Encuentre los segmentos de línea r y t que están respectivamente inmediatamente por encima y por debajo de s en T (si existen); si el cruce de r y t (los vecinos de s en la estructura de datos de estado) forma un posible evento futuro en la cola de eventos, elimine este posible evento futuro de la cola de eventos. Si s cruza r o t , agregue 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 , elimine s de T . Encuentre los segmentos r y t que (antes de la eliminación de s ) estaban respectivamente inmediatamente por encima y por debajo de él en T (si existen). Si r y t se cruzan, agregue ese punto de cruce como un posible evento futuro en la cola de eventos.
    • Si p es el punto de cruce de dos segmentos s y t (con s debajo de t a la izquierda del cruce), 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 cruce rs (es decir, un punto de cruce entre r y s ) y tu (es decir, un punto de cruce 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 cruce a la cola de eventos.

Análisis

El algoritmo procesa un evento por punto final o punto de cruce de segmento, en el orden ordenado de las coordenadas de estos puntos, como se puede probar por inducción. Esto se debe a que, una vez procesado el evento , el siguiente evento (si es un punto de cruce) debe ser un cruce de dos segmentos que sean adyacentes en el orden de los segmentos representados por , y a que el algoritmo mantiene todos los cruces entre segmentos adyacentes como posibles eventos futuros en la cola de eventos; por lo tanto, el siguiente evento correcto siempre estará presente en la cola de eventos. Como consecuencia, encuentra correctamente todos los cruces de segmentos de línea de entrada, el problema que fue diseñado para resolver.

El algoritmo de Bentley-Ottmann procesa una secuencia de eventos, donde denota el número de segmentos de línea de entrada y denota el número de cruces. Cada evento se procesa mediante un número constante de operaciones en el árbol de búsqueda binaria y la cola de eventos, y (debido a que solo contiene puntos finales de segmento y cruces entre segmentos adyacentes) la cola de eventos nunca contiene más de eventos. Todas las operaciones toman tiempo . Por lo tanto, el tiempo total para el algoritmo es .

Si los cruces encontrados por el algoritmo no necesitan ser almacenados una vez que se han encontrado, el espacio utilizado por el algoritmo en cualquier punto en el tiempo es : cada uno de los segmentos de línea de entrada corresponde a lo sumo a un nodo del árbol binario de búsqueda T , y como se indicó anteriormente, la cola de eventos contiene como máximo 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 cuando algún otro evento hace que los dos segmentos de cruce se vuelvan no adyacentes), lo que hace que utilice más espacio. [3]

Chen y Chan (2003) describieron una versión del algoritmo Bentley-Ottmann que utiliza muy poco espacio y que codifica la mayor parte de su información en el orden de los segmentos de una matriz que representa la entrada, requiriendo únicamente celdas de memoria adicionales. Sin embargo, para acceder a la información codificada, el algoritmo se ve ralentizado por un factor logarítmico.

Posición especial

La descripción del algoritmo anterior supone que los segmentos de línea no son verticales, que los puntos finales de los segmentos de línea no se encuentran en 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 que tengan la misma coordenada x . En otras palabras, no tiene en cuenta los casos extremos, es decir, supone la posición general de los puntos finales 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:

En la implementación de LEDA del algoritmo Bentley-Ottmann se utilizó un enfoque similar a las degeneraciones . [4]

Problemas de precisión numérica

Para que el algoritmo sea correcto, es necesario determinar sin aproximación 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 utilizar 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 exactamente, utilizando aritmética de precisión arbitraria . Sin embargo, puede ser posible acelerar los cálculos y comparaciones de estas coordenadas utilizando cálculos de punto flotante y probando si los valores calculados de esta manera están lo 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 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 de la cantidad de bits que las coordenadas de entrada.

Algoritmos más rápidos

La parte O( n log n ) del límite de tiempo para el algoritmo de Bentley–Ottmann es necesaria, ya que hay límites inferiores coincidentes para el problema de detectar segmentos de línea que se cruzan en modelos de árboles de decisión algebraicos de computación. [5] Sin embargo, la dependencia de k , el número de cruces, se puede mejorar. 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 cuyos bordes son las porciones de los segmentos que conectan estos vértices, en el tiempo esperado O( n log n + k ), y este problema de construcción de arreglos se resolvió de manera determinista en el mismo límite de tiempo O( n log n + k ) por Chazelle y Edelsbrunner (1992). Sin embargo, construir este arreglo como un todo requiere un espacio O( n + k ), mayor que el límite espacial O( n ) del algoritmo de Bentley-Ottmann; Balaban (1995) describió un algoritmo diferente que enumera todas las intersecciones en el tiempo O( n log n + k ) y el espacio O( n ).

Si los segmentos de línea de entrada y sus puntos finales forman los bordes y 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 el 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 el tiempo O( n + k log ( i ) n ) para cualquier constante i , donde log ( i ) denota la función obtenida iterando la función logaritmo i veces. El primero de estos algoritmos toma tiempo lineal siempre que k sea mayor que n en un factor log ( i ) n , para cualquier constante i , mientras que el segundo algoritmo toma tiempo lineal siempre que k sea menor que n en un factor log ( i ) n . Ambos algoritmos implican la aplicación del algoritmo Bentley-Ottmann a pequeñas muestras aleatorias de la entrada.

Notas

  1. ^ Shamos y Hoey (1976).
  2. ^ En la descripción del algoritmo en de Berg et al. (2000), la línea de barrido es horizontal y se mueve verticalmente; este cambio implica intercambiar el uso de las coordenadas x e y de manera consistente a lo largo del algoritmo, pero por lo demás no es de gran importancia para la descripción o el análisis del algoritmo.
  3. ^ La complejidad espacial no lineal de la versión original del algoritmo fue analizada por Pach y Sharir (1991).
  4. ^ ab Bartuschka, Mehlhorn y Näher (1997).
  5. ^ Preparata y Shamos (1985), Teorema 7.6, p. 280.

Referencias

Enlaces externos