Una estructura de datos de casco cinético convexo es una estructura de datos cinética que mantiene el casco convexo de un conjunto de puntos en movimiento continuo. [1] Debe distinguirse de las estructuras de datos dinámicas de casco convexo , 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 del casco convexo cinético bidimensional es la de Basch, Guibas y Hershberger. Esta estructura de datos es receptiva , eficiente , compacta y local . [1]
La estructura de datos
El dual de un casco convexo de un conjunto de puntos es la envolvente 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 el casco convexo 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 el casco convexo 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 conquistar que divide las líneas en dos conjuntos de igual tamaño, se llama a sí mismo de forma recursiva en los dos conjuntos para encontrar sus envolventes superiores y luego fusiona las dos envolventes superiores resultantes . El paso de fusión se realiza mediante 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 envolventes superiores barre todos los vértices de las envolventes superiores rojas y azules, de izquierda a derecha. Los puntos rojos y azules encontrados más recientemente se mantienen a medida que se desplaza la línea. 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 al sobre superior combinado. Si es de un color diferente al último punto agregado, los sobres rojo y azul se han cruzado, por lo que el punto de intersección también se agrega al sobre superior combinado. [2]
La secuencia de aristas y vértices resultante de este algoritmo solo depende del orden de los puntos y de los resultados de las comparaciones entre líneas y puntos. Así, el resultado se puede certificar con los siguientes certificados:
- 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. Dado que cada punto consta de 2 líneas y el certificado incluye 2 puntos, cada certificado consta de 4 líneas.
- certificados y) se utilizan para certificar que un vértice está por encima o por debajo de un borde. Los certificados aparecen para todas las comparaciones que se producirían durante el algoritmo.
Mientras se mantengan todos estos certificados, los pasos de combinación se ejecutarán de manera idéntica, por lo que el sobre superior resultante será el mismo. Se puede crear una estructura de datos cinética para 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 del otro sobre.
Por lo tanto, es necesario introducir un certificado s () que certifica que la pendiente de una línea es mayor o menor que la pendiente de otra línea.
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]
- : . denota el vértice más cercano a a su derecha. Este certificado se almacena para todos los puntos. que tienen un color diferente al de la punta, , que les sigue.
- : o . Este certificado se almacena para todos los puntos. tal que se cruza . denota el borde contendiente de , el borde del otro sobre que está arriba o abajo .
- : o . Este certificado se almacena para todos los puntos. tal que se cruza .
- : . Este certificado se almacena para todos los puntos. para cual y .
- : . Este certificado se almacena para todos los puntos. para cual y .
- : . Este certificado se almacena para todos los puntos. para cual y .
- : . Este certificado se almacena para todos los puntos. para cual y .
- : . Este certificado se almacena para todos los puntos. para cual y .
El primer certificado, , certifica el ordenamiento x de los puntos en los sobres rojo y azul. El segundo y tercer certificado, y , certificar las intersecciones de los sobres rojo y azul. Los 5 certificados restantes,, , , , y coloque los bordes que no están en los sobres superiores en la secuencia de pendientes de los bordes que están por encima. Si la pendiente está al principio o al final de la secuencia, o certificar esto. Si está en el medio de la secuencia, y certificar esto, y certifica que el punto de intersección de las dos líneas entre las que se encuentra la pendiente del borde está por encima de él. Estos uno o tres certificados son suficientes para demostrar que todos los bordes están por encima de esta línea. A diferencia del esquema anterior, todas las líneas solo están involucradas en un número constante de certificados. Siempre que estos certificados fallen, el sobre y los certificados combinados se pueden actualizar en O (1) tiempo.
La estructura de datos cinéticos para el casco convexo se construye utilizando estos certificados para certificar la fusión recursiva de las envolventes superiores. Siempre que los certificados fallan, su combinación se actualiza y, si el sobre resultante de la combinación cambia, los cambios se propagan hacia arriba a través de todas las combinaciones que dependen del resultado de la combinación. [1]
Actuación
Esta estructura de datos es receptiva , local , compacta y eficiente . Esto se debe a la profundidad logarítmica de las fusiones utilizadas para certificar la envolvente superior. [1]
- Responsive: cuando falla un certificado, se necesita O (1) para corregir la combinación que certifica. Si la envolvente resultante cambia, el cambio debe propagarse a todas las fusiones que dependen del resultado de la fusión modificada. Hay O (log n ) tales fusiones, por lo que la actualización se puede realizar en O (log n ) total de tiempo.
- Local: cada línea está involucrada en la mayoría de los certificados O (log n ). Esto se debe a que cada línea está involucrada en un número constante de certificados en cada combinación, y cada línea está en el total de combinaciones O (log n ).
- 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 combinación implica un número de certificados lineales al número de líneas combinadas. La certificación de un sobre superior de n líneas requiere certificados para la combinación del sobre superior de los dos subconjuntos de n / 2 líneas y certificados para la combinación de los sobres. Así, el número de certificados, C ( n ), necesarios para certificar la envolvente superior de n líneas satisface la recurrencia C ( n ) = 2C ( n / 2) + O ( n ), con C (1) = O (1) . Según el teorema maestro para las 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 pseudo-algebraicas es casi cuadrático, para todos . [3] [4] Los cascos convexos de puntos que se mueven linealmente pueden cambiarveces. [5] Por tanto, esta estructura de datos es eficiente.
Mayores dimensiones
Encontrar una estructura de datos cinética eficiente para mantener el casco convexo de los puntos móviles en dimensiones superiores a 2 es un problema abierto. [1]
Problemas relacionados
El casco cinético convexo se puede utilizar para resolver los siguientes problemas relacionados: [6]
Referencias
- ^ a b c d e f Basch, Julien; Guibas, Leonidas J .; Hershberger, John (abril de 1999). "Estructuras de datos para datos móviles" (PDF) . J. Algoritmos . 31 (1): 1–28. CiteSeerX 10.1.1.134.6921 . doi : 10.1006 / jagm.1998.0988 .
- ^ Hershberger, John (21 de diciembre de 1989). "Encontrar la envolvente superior de n segmentos de línea en el tiempo O ( n log n )". Cartas de procesamiento de información . 33 (4): 169-174. doi : 10.1016 / 0020-0190 (89) 90136-1 .
- ^ Agarwal, Pankaj K .; Schwarzkopf, Otfried; Sharir, Micha (enero de 1996). "La superposición de sobres inferiores y sus aplicaciones". Geometría discreta y computacional . 15 (1): 1–13. CiteSeerX 10.1.1.54.5488 . doi : 10.1007 / BF02716576 .
- ^ Sharir, Micha (1994). "Límites superiores casi ajustados para envolventes inferiores en dimensiones superiores. Geometría discreta y computacional" . Geometría discreta y computacional . 12 (1): 327–345. doi : 10.1007 / BF02574384 .
- ^ Agarwal, Pankaj K .; Guibas, Leonidas J .; Hershberger, John; Veach, Eric (enero de 2001). "Mantener la extensión de un conjunto de puntos móviles". Geometría discreta y computacional . 26 (3): 353–374. CiteSeerX 10.1.1.47.8510 . doi : 10.1007 / s00454-001-0019-x .
- ^ Agarwal, Pankaj K .; Guibas, Leonidas J .; Hershberger, John; Veach, Eric (agosto de 1997). "Mantener la extensión de un conjunto de puntos móviles" . Notas de la clase en Ciencias de la Computación Volumen 1272 . V Workshop de Algoritmos y Estructuras de Datos (WADS '97) . págs. 31–44. doi : 10.1007 / 3-540-63307-3_46 .