Lista ordenada cinéticamente

Estructura de datos cinéticos

Una lista ordenada cinética es una estructura de datos cinéticos que permite mantener una lista de puntos en movimiento ordenados. Se utiliza como estructura de datos predecesora cinética y como componente en estructuras de datos cinéticos más complejas, como el par más cercano cinético .

Implementación

Esta estructura de datos mantiene una lista de los elementos ordenados, y los certificados imponen el orden entre elementos adyacentes. Cuando un certificado falla, se intercambian los elementos en cuestión. Luego, se deben actualizar como máximo tres certificados: el certificado del par intercambiado, los dos certificados que incluyen los elementos intercambiados y los elementos de la lista ordenada que preceden y siguen directamente al par intercambiado.

Por ejemplo, dada una lista ordenada {A,B,C,D,E,F}, los certificados serán [A<B], [B<C], [C<D], [D<E], [E<F]. Si el certificado [C<D] falla, la lista se actualizará a {A,B,D,C,E,F}, y los certificados [B<C], [C<D] y [D<E] se reemplazarán por [B<D], [D<C] y [C<E], respectivamente. El nuevo conjunto de certificados será [A<B], [B<D], [D<C], [C<E], [E<F]

Análisis

Esta estructura de datos cinéticos es:

• Responsive : una falla de certificado provoca un intercambio (que demora O(1) tiempo) y O(1) cambios de certificado que demoran O(log n) tiempo para reprogramarse
• Local : cada elemento está involucrado en como máximo 2 certificados
• Compacto : hay exactamente n -1 certificados para una lista de n elementos
• Eficiente : esta estructura de datos no provoca eventos internos extraños , cada cambio en el orden de los elementos provoca exactamente una falla de certificado.

Generalización

Esta estructura de datos se puede generalizar a una estructura de datos cinética que puede devolver una lista ordenada de puntos en el tiempo y procesar eventos en total, suponiendo trayectorias pseudoalgebraicas , donde es un parámetro de la estructura de datos. Por lo tanto, se puede lograr un equilibrio entre el tiempo de mantenimiento y el tiempo de consulta para adaptarse a aplicaciones específicas. ${\displaystyle O(n\log m)}$ ${\displaystyle O({\frac {n^{2}}{m}})}$ ${\displaystyle m}$

En la estructura de datos generalizada, los puntos se dividen arbitrariamente en m subconjuntos de tamaño , y se mantienen listas ordenadas cinéticamente en los subconjuntos. Cada sublista ordenada necesita procesar eventos (errores de certificados) como máximo, ya que hay intercambios de cada uno de los pares de elementos. Por lo tanto, el tiempo total necesario para mantener la estructura de datos es . Las solicitudes de la lista ordenada se pueden responder en fusionando las sublistas ordenadas con mergesort . ${\displaystyle O({\frac {n}{m}})}$ ${\displaystyle O({\frac {n^{2}}{m^{2}}})}$ ${\displaystyle O(1)}$ ${\displaystyle O({\frac {n^{2}}{m^{2}}})}$ ${\displaystyle O({\frac {n^{2}}{m}})}$ ${\displaystyle O(n\log m)}$

Referencias

• Abam, MA; De Berg, M. (2007), "Clasificación cinética y envolturas convexas cinéticas", Número especial del vigésimo primer simposio anual sobre geometría computacional — SoCG 2005, Geometría computacional: teoría y aplicaciones , 37 (1): 16–26, doi :10.1016/j.comgeo.2006.02.004.