Lista ordenada cinética

Una lista ordenada cinética es una estructura de datos cinética para mantener una lista de puntos en movimiento en orden ordenado. Se utiliza como una estructura de datos cinética predecesora y como un componente en estructuras de datos cinéticas más complejas, como el par cinético más cercano .

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

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 el total de eventos, asumiendo trayectorias pseudoalgebraicas , donde es un parámetro de la estructura de datos. Por lo tanto, se puede hacer una compensación de tiempo de mantenimiento versus tiempo de consulta para sintonizar 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 las listas ordenadas cinéticamente se mantienen en los subconjuntos. Cada sublista ordenada necesita procesar eventos (fallos de certificado) como máximo, ya que hay intercambios de cada uno de los pares de elementos. Por tanto, el tiempo total necesario para mantener la estructura de datos es . Las solicitudes de la lista ordenada se pueden responder combinando las sublistas ordenadas con mergesort . ${\ Displaystyle O ({\ frac {n} {m}})}$ $O({\frac {n^{2}}{m^{2}}})$ $O(1)$ $O({\frac {n^{2}}{m^{2}}})$ $O({\frac {n^{2}}{m}})$ $O(n\log m)$