Envolvente convexa cinética

Una estructura de datos de envoltura convexa cinética es una estructura de datos cinética que mantiene la envoltura convexa de un conjunto de puntos en movimiento continuo. ^[1] Debe distinguirse de las estructuras de datos de envoltura convexa dinámicas , que manejan puntos que experimentan cambios discretos, como inserciones o eliminaciones de puntos, en lugar de un movimiento continuo.

El caso 2D

La estructura de datos más conocida para el problema de la envoltura convexa cinética bidimensional es la de Basch, Guibas y Hershberger. Esta estructura de datos es responsiva , eficiente , compacta y local . ^[1]

La estructura de datos

El dual de una envoltura convexa de un conjunto de puntos son las envolventes superior e inferior del conjunto dual de líneas. Por lo tanto, mantener las envolventes superior e inferior de un conjunto de líneas en movimiento es equivalente a mantener la envoltura convexa de un conjunto de puntos en movimiento. Calcular las envolventes superior e inferior son problemas equivalentes, por lo que calcular la envolvente superior de un conjunto de líneas es equivalente a calcular la envoltura convexa de un conjunto de puntos en movimiento. La envolvente superior de un conjunto de líneas estáticas se puede calcular utilizando un algoritmo de dividir y vencer que divide las líneas en dos conjuntos de igual tamaño, se llama a sí mismo recursivamente en los dos conjuntos para encontrar sus envolventes superiores y luego fusiona las dos envolventes superiores resultantes. El paso de fusión se realiza utilizando un barrido de línea vertical . Llame al primer conjunto de puntos azul y al segundo conjunto de puntos rojo.

El algoritmo de barrido de línea estándar para fusionar las envolventes superiores recorre todos los vértices de las envolventes superior roja y azul, de izquierda a derecha. Los puntos rojo y azul encontrados más recientemente se mantienen a medida que la línea barre. Cuando se encuentra un punto, el algoritmo verifica si el punto está por encima o por debajo del segmento que sigue al último punto encontrado del color opuesto. Si está por encima, ese punto se agrega a la envolvente superior fusionada. Si es de un color diferente al último punto agregado, las envolventes roja y azul se han cruzado, por lo que el punto de intersección también se agrega a la envolvente superior fusionada. ^[2]

La secuencia de aristas y vértices resultante de este algoritmo depende únicamente del orden de los puntos y de los resultados de las comparaciones de líneas y puntos. Por tanto, el resultado puede certificarse con los siguientes certificados:

• Los certificados x ( ) se utilizan para certificar el orden de los vértices de los sobres rojo y azul. Son los certificados para una lista ordenada cinéticamente en el conjunto de vértices. Como cada punto implica 2 líneas y el certificado implica 2 puntos, cada certificado implica 4 líneas. ${\displaystyle <_{x}}$
• Los certificados y ( ) se utilizan para certificar que un vértice está por encima o por debajo de una arista. Los certificados aparecen para todas las comparaciones que se producirían durante el algoritmo. ${\displaystyle <_{y}}$

Mientras se cumplan todos estos certificados, los pasos de fusión se ejecutarán de forma idéntica, por lo que la envolvente superior resultante será la misma. Se puede crear una estructura de datos cinética para las envolventes superiores utilizando estos certificados para certificar el algoritmo de envolvente superior estático. Sin embargo, este esquema no es local, porque una línea puede estar involucrada en muchos certificados y si permanece en la parte superior o inferior, ya que se encuentran muchos puntos de la otra envolvente.

Por lo tanto, es necesario introducir un certificado s ( ) que certifique que la pendiente de una línea es mayor o menor que la pendiente de otra línea. ${\displaystyle <_{s}}$

Tener los siguientes certificados para todos los puntos ab es suficiente para certificar la secuencia de aristas y vértices resultante de una fusión, con solo O(1) certificados por línea: ^[1]

Los certificados certifican la estructura de la intersección de los sobres rojo y azul certificando las intersecciones (arriba a la izquierda) o la ausencia de intersecciones (arriba a la derecha y abajo). Las flechas indican qué elementos se comparan en el certificado.

1. ${\displaystyle x[ab]}$: . indica el vértice más cercano a su derecha. Este certificado se almacena para todos los puntos que tienen un color diferente al del punto , que los sigue. ${\displaystyle ab<_{x}ab.next}$ ${\displaystyle ab.next}$ ${\displaystyle ab}$ ${\displaystyle ab}$ ${\displaystyle ab.next}$
2. ${\displaystyle yli[ab]}$: o . Este certificado se almacena para todos los puntos tales que interseca . denota el borde contendiente de , el borde del otro sobre que está por encima o por debajo de . ${\displaystyle ab<_{y}ce(ab)}$ ${\displaystyle ab>_{y}ce(ab)}$ ${\displaystyle ab}$ ${\displaystyle b}$ ${\displaystyle ce(ab)}$ ${\displaystyle ce(ab)}$ ${\displaystyle ab}$ ${\displaystyle ab}$
3. ${\displaystyle yri[ab]}$: o . Este certificado se almacena para todos los puntos que interseca . ${\displaystyle ab<_{y}ce(ab)}$ ${\displaystyle ab>_{y}ce(ab)}$ ${\displaystyle ab}$ ${\displaystyle a}$ ${\displaystyle ce(ab)}$
4. ${\displaystyle yt[ab]}$: . Este certificado se almacena para todos los puntos para los que y . ${\displaystyle ce(ab)<_{y}ab}$ ${\displaystyle ab}$ ${\displaystyle a<_{s}ce(ab)<_{s}b}$ ${\displaystyle ce(ab)<_{y}ab}$
5. ${\displaystyle srt[ab]}$: . Este certificado se almacena para todos los puntos para los que y . ${\displaystyle a<_{s}ce(ab)}$ ${\displaystyle ab}$ ${\displaystyle a<_{s}ce(ab)<_{s}b}$ ${\displaystyle ce(ab)<_{y}ab}$
6. ${\displaystyle srt[ab]}$: . Este certificado se almacena para todos los puntos para los que y . ${\displaystyle ce(ab)<_{s}b}$ ${\displaystyle ab}$ ${\displaystyle a<_{s}ce(ab)<_{s}b}$ ${\displaystyle ce(ab)<_{y}ab}$
7. ${\displaystyle sl[ab]}$: . Este certificado se almacena para todos los puntos para los que y . ${\displaystyle b<_{s}ce(ab)}$ ${\displaystyle ab}$ ${\displaystyle b<_{s}ce(ab)}$ ${\displaystyle ab<_{y}ce(ab)}$
8. ${\displaystyle sr[ab]}$: . Este certificado se almacena para todos los puntos para los que y . ${\displaystyle ce(ab)<_{s}a}$ ${\displaystyle ab}$ ${\displaystyle ce(ab)<_{s}a}$ ${\displaystyle ab<_{y}ce(ab)}$

El primer certificado, , certifica el orden x de los puntos en las envolventes roja y azul. El segundo y tercer certificado, y , certifican las intersecciones de las envolventes roja y azul. Los 5 certificados restantes, , , , y colocan las aristas que no están en las envolventes superiores en la secuencia de pendientes de las aristas que están por encima de ella. Si la pendiente está al principio o al final de la secuencia, o certifican esto. Si está en el medio de la secuencia , y certifican esto, y certifican que el punto de intersección de las dos líneas entre las que está la pendiente de la arista, está por encima de ella. Estos uno o tres certificados son suficientes para demostrar que todas las aristas están por encima de esta línea. A diferencia del esquema anterior, todas las líneas solo participan en un número constante de certificados. Siempre que uno de estos certificados falla, la envolvente y los certificados fusionados se pueden actualizar en tiempo O(1). ${\displaystyle x[ab]}$ ${\displaystyle yli[ab]}$ ${\displaystyle yri[ab]}$ ${\displaystyle yt[ab]}$ ${\displaystyle srt[ab]}$ ${\displaystyle srt[ab]}$ ${\displaystyle sl[ab]}$ ${\displaystyle sr[ab]}$ ${\displaystyle sl}$ ${\displaystyle sr}$ ${\displaystyle slt}$ ${\displaystyle srt}$ ${\displaystyle yt}$

La estructura de datos cinéticos para la envoltura convexa se construye utilizando estos certificados para certificar la fusión recursiva de las envolturas superiores. Cuando los certificados fallan, se actualiza su fusión y, si la envoltura resultante de la fusión cambia, los cambios se propagan hacia arriba a través de todas las fusiones que dependen del resultado de la fusión. ^[1]

Actuación

Esta estructura de datos es responsiva , local , compacta y eficiente . Esto se debe a la profundidad logarítmica de las fusiones utilizadas para certificar la envolvente superior. ^[1]

• Responsive: Cuando un certificado falla, se necesitan O(1) para reparar la fusión que certifica. Si el sobre resultante cambia, el cambio debe propagarse a todas las fusiones que dependen del resultado de la fusión modificada. Existen O(log n ) fusiones de este tipo, por lo que la actualización se puede realizar en un tiempo total de O(log n ).
• Local: cada línea está involucrada en un máximo de O(log n ) certificados. Esto se debe a que cada línea está involucrada en una cantidad constante de certificados en cada fusión y cada línea está involucrada en un total de O(log n ) fusiones.
• Compacidad: El número máximo de certificados utilizados en esta estructura de datos es O( n log n ). Esto se debe a que cada fusión implica un número de certificados lineal al número de líneas fusionadas. La certificación de una envolvente superior de n líneas requiere certificados para la envolvente superior de fusión de los dos subconjuntos de n /2 líneas y certificados para la fusión de las envolventes. Por lo tanto, el número de certificados, C( n ), necesario para certificar la envolvente superior de n líneas satisface la recurrencia C( n )=2C( n /2)+O( n ), con C(1)=O(1). Por el teorema maestro para recurrencias de divide y vencerás , C( n )=O( n log n ).
• Eficiencia: El número máximo de eventos procesados ​​por este algoritmo en trayectorias algebraicas o pseudoalgebraicas es casi cuadrático, para todos los . ^{[3] [4]} Las envolturas convexas de puntos en movimiento lineal pueden cambiar los tiempos. ^[5] Por lo tanto, esta estructura de datos es eficiente. ${\displaystyle O(n^{2+\epsilon })}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \Omega (n^{2})}$

Dimensiones superiores

Encontrar una estructura de datos cinéticos eficiente para mantener la envoltura convexa de puntos en movimiento en dimensiones superiores a 2 es un problema abierto. ^[1]

Problemas relacionados

La envoltura convexa cinética se puede utilizar para resolver los siguientes problemas relacionados: ^[6]

• Diámetro cinético
• Ancho cinético
• Caja mínima cinética
• Disco envolvente cinético más pequeño

Referencias

1. Basch, Julien; Guibas, Leonidas J .; Hershberger, John (abril de 1999). "Estructuras de datos para datos móviles" (PDF) . Journal of Algorithms . 31 (1): 1–28. CiteSeerX  10.1.1.134.6921 . doi :10.1006/jagm.1998.0988. S2CID  8013433.
2. Hershberger, John (21 de diciembre de 1989). "Encontrar la envolvente superior de n segmentos de línea en tiempo O( n log n )". Information Processing Letters . 33 (4): 169–174. doi :10.1016/0020-0190(89)90136-1.
3. Agarwal, Pankaj K .; Schwarzkopf, Otfried; Sharir, Micha (enero de 1996). "La superposición de envolventes inferiores y sus aplicaciones". Geometría discreta y computacional . 15 (1): 1–13. CiteSeerX 10.1.1.54.5488 . doi :10.1007/BF02716576. S2CID  1261935. 
4. Sharir, Micha (1994). "Límites superiores casi estrictos para envolventes inferiores en dimensiones superiores". Geometría discreta y computacional . 12 (1): 327–345. doi : 10.1007/BF02574384 .
5. Agarwal, Pankaj K. ; Guibas, Leonidas J. ; Hershberger, John; Veach, Eric (enero de 2001). "Mantenimiento de la extensión de un conjunto de puntos en movimiento". Geometría discreta y computacional . 26 (3): 353–374. CiteSeerX 10.1.1.47.8510 . doi :10.1007/s00454-001-0019-x. 
6. Agarwal, Pankaj K. ; Guibas, Leonidas J. ; Hershberger, John; Veach, Eric (agosto de 1997). "Mantenimiento de la extensión de un conjunto de puntos en movimiento". Lecture Notes in Computer Science Volume 1272 . 5.º Taller sobre algoritmos y estructuras de datos (WADS '97). págs. 31–44. doi :10.1007/3-540-63307-3_46.