Estructura de datos cinéticos

Una estructura de datos cinética es una estructura de datos utilizada para rastrear un atributo de un sistema geométrico que se mueve continuamente. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} Por ejemplo, una estructura de datos de envolvente convexa cinética mantiene la envolvente convexa de un grupo de${\displaystyle n}$Puntos en movimiento. El desarrollo de estructuras de datos cinéticos fue motivado por problemas de geometría computacional que involucran objetos físicos en movimiento continuo, como la detección de colisiones o visibilidad en robótica, animación o gráficos por computadora.

Las estructuras de datos cinéticas se utilizan en sistemas donde hay un conjunto de valores que cambian en función del tiempo, de una manera conocida. Entonces el sistema tiene algunos valores, y para cada valor${\displaystyle v}$, se sabe que${\displaystyle v=f(t)}$Las estructuras de datos cinéticas permiten realizar consultas sobre un sistema en el tiempo virtual actual.${\displaystyle t}$y dos operaciones adicionales:

• ${\displaystyle {\textrm {avance}}(t)}$: Avanza el sistema al tiempo${\displaystyle t}$.
• ${\displaystyle {\textrm {cambio}}(v,f(t))}$Altera la trayectoria del valor${\displaystyle v}$a${\displaystyle f(t)}$, a partir de este momento.

Es posible que se admitan operaciones adicionales. Por ejemplo, las estructuras de datos cinéticas se suelen utilizar con un conjunto de puntos. En este caso, la estructura normalmente permite insertar y eliminar puntos.

Una estructura de datos cinética permite que los valores almacenados en ella cambien continuamente con el tiempo. En principio, esto se puede aproximar muestreando la posición de los puntos a intervalos fijos y eliminando y reinsertando cada punto en una estructura de datos "estática" (tradicional). Sin embargo, este enfoque es vulnerable al sobremuestreo o al submuestreo, dependiendo del intervalo de tiempo utilizado, y también puede resultar ineficiente en términos de recursos computacionales.

El siguiente enfoque general puede utilizarse para construir estructuras de datos cinéticos: ^{[ 5 ]}

1. Almacenar una estructura de datos en el sistema en el momento actual.${\displaystyle t}$Esta estructura de datos permite realizar consultas sobre el sistema en el momento virtual actual.
2. Amplíe la estructura de datos con certificados. Los certificados son condiciones bajo las cuales la estructura de datos es precisa. Todos los certificados son verdaderos actualmente, y la estructura de datos solo dejará de ser precisa cuando alguno de ellos deje de serlo.
3. Calcula el tiempo de fallo de cada certificado, es decir, el momento en que dejará de ser válido.
4. Almacene los certificados en una cola de prioridad , indexada por sus tiempos de fallo.
5. Para avanzar al tiempo${\displaystyle t}$, examine el certificado con el menor tiempo de fallo de la cola de prioridad. Si el certificado falla antes de tiempo${\displaystyle t}$, elimínelo de la cola y corrija la estructura de datos para que sea precisa en el momento del fallo, y actualice los certificados. Repita esto hasta que el certificado con el menor tiempo de fallo en la cola de prioridad falle después de un tiempo${\displaystyle t}$. Si el certificado con el menor tiempo de fallo en la cola de prioridad falla después de un tiempo${\displaystyle t}$, entonces todos los certificados son verdaderos en ese momento.${\displaystyle t}$para que la estructura de datos pueda responder correctamente a las consultas en el momento${\displaystyle t}$.

El enfoque se puede resumir en pseudocódigo de la siguiente manera. La estructura de datos Des válida en el momento actual nowy se amplía con una cola de prioridad Qde certificados indexados por tiempo de fallo:

función avance(t): mientras Q no esté vacío y minFailureTime(Q) ≤ t: c := extractMin(Q) (el certificado que falla) ahora := tiempoFracaso(c) reparar D para que sea preciso en este momento eliminar certificados no válidos de Q calcular los tiempos de fallo de los nuevos certificados insertar los nuevos certificados en Q ahora := t (todos los certificados son válidos en el momento t)

función change(v, f): (cambio de trayectoria, a partir del momento actual) para cada certificado c en Q que involucre a v: recalcular failureTime(c) y actualizar su clave en Q

El número de certificados que involucran un mismo valor, que delimita el trabajo realizado por change, es la localidad de la estructura.

Al utilizar el enfoque de certificados, existen cuatro medidas de rendimiento. Decimos que una cantidad es pequeña si es una función polilogarítmica de${\displaystyle n}$, o es${\displaystyle O(n^{\epsilon })}$para cantidades arbitrariamente pequeñas${\displaystyle \epsilon }$, dónde${\displaystyle n}$es el número de objetos:

El enfoque de certificados asume que los eventos se procesan uno a uno, en orden, en sus momentos exactos de falla de valor real. Muchos sistemas que rastrean objetos en movimiento, como simulaciones físicas y servidores de juegos, observan el mundo en intervalos de tiempo fijos. Entre observaciones, pueden fallar varios certificados, por lo que la estructura de datos debe reparar un lote de fallas en cada paso en lugar de una sola falla en un momento exacto. Guibas identifica la recuperación después de múltiples fallas de certificados como un problema estructural abierto para el marco. ^{[ 2 ]}

Una sutileza relacionada es que un conjunto de certificados puede constituir una prueba histórica : certifica el atributo solo en combinación con el hecho de que ningún certificado falló anteriormente en el proceso. Si el sistema puede cambiar entre observaciones, puede requerirse una prueba absoluta , un conjunto de certificados que valide el atributo en cualquier estado del mundo. ^{[ 2 ]}

Cuando se conocen las trayectorias y los tiempos de falla se cuantifican en pasos de tiempo enteros, la cola de prioridad de certificados puede reemplazarse por una cola de cubetas indexada por número de paso, lo que reduce la programación y extracción de eventos a un tiempo constante por operación. ^{[ 6 ]}

Las implementaciones de estructuras de datos cinéticas deben calcular los tiempos de fallo de los certificados hallando las raíces de polinomios, lo que plantea problemas de robustez numérica ausentes en el modelo teórico, donde se asume la búsqueda exacta de raíces en tiempo constante. Russel estudió enfoques exactos y filtrados para la planificación de eventos y los costes prácticos de mantener la cola de eventos en implementaciones de triangulaciones de Delaunay cinéticas y estructuras relacionadas. ^{[ 7 ]}

Los enfoques cinéticos para la detección de colisiones pueden limitar el número de eventos mediante la separación relativa de los objetos en lugar de mediante una tasa de muestreo fija, evitando tanto el sobremuestreo como el submuestreo. ^{[ 8 ]} En aplicaciones interactivas como juegos y motores de física, el algoritmo de barrido y poda de fase amplia, ampliamente utilizado, mantiene órdenes ordenadas de los extremos de los cuadros delimitadores y los repara incrementalmente a medida que los objetos se mueven, y puede considerarse como una estructura de datos cinética cuyos certificados son las adyacencias en los órdenes ordenados. ^{[ 9 ]}

Un obstáculo práctico para una mayor adopción es el costo de los cambios de trayectoria: cada certificado que involucra un objeto debe reevaluarse cuando cambia el movimiento de ese objeto, lo cual la medida de localidad está diseñada para limitar. ^{[ 2 ]} Se han propuesto descripciones de movimiento jerárquicas, en las que los objetos cercanos comparten componentes de movimiento, para reducir este costo. ^{[ 2 ]}

La encuesta de Guibas enumera varios problemas que siguen abiertos, entre ellos encontrar una estructura de datos cinéticos eficiente, receptiva, local y compacta para la envoltura convexa de puntos que se mueven en dimensión tres o superior; reducir la brecha entre el límite inferior cuadrático y el límite superior casi cúbico en el número de eventos del diagrama de Voronoi cinético ; mantener un árbol de expansión mínima euclidiano cinético con un número subcuadrático de eventos; y desarrollar análisis sensibles al movimiento cuyos costos se parametrizan por la coherencia del movimiento en lugar de por el peor caso. ^{[ 2 ]} Las cuestiones estructurales incluyen la recuperación después de múltiples fallos de certificados y el análisis de estructuras no canónicas dependientes del historial, para las cuales faltan técnicas matemáticas. ^{[ 2 ]}

Rahmati mejoró el límite de eventos para el árbol de expansión mínima euclidiana cinética en el plano desde${\displaystyle O(n^{4})}$aproximadamente${\displaystyle O(n^{3}\log n)}$hasta factores de Davenport-Schinzel , y plantearon problemas sucesores que incluyen un árbol de expansión mínima euclidiano cinético con un número subcúbico de eventos y una respuesta en el peor de los casos en lugar de amortizada para estructuras de vecinos más cercanos cinéticas. ^{[ 4 ]}

El rendimiento de una determinada estructura de datos cinéticos puede analizarse para ciertos tipos de trayectorias. Normalmente, se consideran los siguientes tipos de trayectorias:

• Afines : (Funciones lineales)${\displaystyle f(t)=at+b}$
• Funciones algebraicas de grado acotado : (Funciones polinómicas de grado acotado)${\displaystyle f(t)=\sum _{i=0}^{n}a_{i}t^{i}}$para algún fijo${\displaystyle n}$.
• Pseudoalgebraico : Trayectorias tales que cualquier certificado de interés alterna entre verdadero y falso.${\displaystyle O(1)}$ veces.

• Torneo cinético
• Lista ordenada cinética
• Montón cinético
• envolvente convexa cinética
• Par más cercano cinético
• Árbol de expansión mínima cinética
• Árbol de expansión mínima euclidiano cinético
• Gráfico cinético de Yao ^{[ 4 ]}
• Gráfico semi-Yao cinético (una variante del gráfico theta ) ^{[ 4 ]}
• Cinética de todos los vecinos más cercanos ^{[ 4 ]}
• Cinética de todos los k vecinos más cercanos ^{[ 4 ]}