Estructura de datos cinéticos

Estructuras de datos utilizadas para rastrear cuerpos geométricos en movimiento continuo

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

Descripción general

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

• ${\displaystyle {\textrm {advance}}(t)}$:Avanza el sistema hacia el tiempo . ${\displaystyle t}$
• ${\displaystyle {\textrm {change}}(v,f(t))}$:Altera la trayectoria del valor a , a partir del momento actual. ${\displaystyle v}$ ${\displaystyle f(t)}$

Se pueden admitir operaciones adicionales. Por ejemplo, las estructuras de datos cinéticos se utilizan a menudo con un conjunto de puntos. En este caso, la estructura suele permitir la inserción y eliminación de puntos.

Contraste con las estructuras de datos tradicionales

Una estructura de datos cinética permite que los valores almacenados en ella cambien continuamente con el tiempo. En principio, esto se puede lograr tomando muestras de la posición de los puntos a intervalos fijos de tiempo y eliminando y reinsertando cada punto en una estructura de datos "estática" (tradicional). Sin embargo, este enfoque es vulnerable al sobremuestreo o submuestreo, según el intervalo de tiempo que se utilice, y también puede desperdiciar recursos computacionales.

Enfoque de certificados

Se puede utilizar el siguiente enfoque general para construir estructuras de datos cinéticos: ^[5]

1. Almacena una estructura de datos en el sistema en el momento actual . Esta estructura de datos permite realizar consultas en el sistema en el momento virtual actual. ${\displaystyle t}$
2. Aumente la estructura de datos con certificados. Los certificados son condiciones bajo las cuales la estructura de datos es precisa. Ahora todos los certificados son verdaderos y la estructura de datos solo dejará de ser precisa cuando uno de los certificados ya no lo sea.
3. Calcular el tiempo de fallo de cada certificado, el momento en el que dejará de ser verdadero.
4. Almacene los certificados en una cola de prioridad, ordenados según sus tiempos de falla.
5. Para avanzar a time , observe el certificado con el tiempo de falla más bajo de la cola de prioridad. Si el certificado falla antes de time , sáquelo de la cola y corrija la estructura de datos para que sea precisa en el momento de la falla y actualice los certificados. Repita esto hasta que el certificado con el tiempo de falla más bajo en la cola de prioridad falle después de time . Si el certificado con el tiempo de falla más bajo en la cola de prioridad falla después de time , entonces todos los certificados son verdaderos en time para que la estructura de datos pueda responder correctamente las consultas en time . ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$

Tipos de eventos

Los fallos de los certificados se denominan "eventos". Un evento se considera interno si la propiedad que mantiene la estructura de datos cinéticos no cambia cuando se produce el evento. Un evento se considera externo si la propiedad que mantiene la estructura de datos cambia cuando se produce el evento.

Actuación

Cuando se utiliza el método de los certificados, hay cuatro medidas de rendimiento. Decimos que una cantidad es pequeña si es una función polilogarítmica de , o es para un número arbitrariamente pequeño de , donde es el número de objetos: ${\displaystyle n}$ ${\displaystyle O(n^{\epsilon })}$ ${\displaystyle \epsilon }$ ${\displaystyle n}$

Sensibilidad

La capacidad de respuesta es el tiempo que se requiere en el peor de los casos para reparar la estructura de datos y ampliar los certificados cuando falla un certificado. Una estructura de datos cinética responde si el tiempo que se requiere en el peor de los casos para una actualización es pequeño.

Localidad

La cantidad máxima de certificados en los que participa un valor determinado. Para las estructuras que involucran puntos en movimiento, esta es la cantidad máxima de certificados en los que participa un punto determinado. Una estructura de datos cinética es local si la cantidad máxima de certificados en los que participa un valor determinado es pequeña.

Compacidad

La cantidad máxima de certificados que se utilizan para aumentar la estructura de datos en cualquier momento. Una estructura de datos cinética es compacta si la cantidad de certificados que utiliza es o para un número arbitrariamente pequeño (un factor pequeño mayor que el espacio lineal). ${\displaystyle O(n\operatorname {polylog} n)}$ ${\displaystyle O(n^{1+\epsilon })}$ ${\displaystyle \epsilon }$

Eficiencia

La relación entre el número de eventos en el peor de los casos que pueden ocurrir cuando se avanza en la estructura y el número de "cambios necesarios" en el peor de los casos en la estructura de datos. La definición de "cambios necesarios" depende del problema. Por ejemplo, en el caso de una estructura de datos cinética que mantiene la envoltura cinética de un conjunto de puntos en movimiento, la cantidad de cambios necesarios sería la cantidad de veces que cambia la envoltura cinética a medida que avanza el tiempo hasta . Se dice que una estructura de datos cinética es eficiente si esta relación es pequeña. ${\displaystyle t=\infty }$ ${\displaystyle t=\infty }$

Tipos de trayectorias

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

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

Ejemplos

• Torneo cinético
• Lista ordenada cinéticamente
• Montón cinético
• Envoltura convexa cinética
• Par cinético más cercano
• Árbol de expansión mínima cinética
• Árbol de expansión mínima euclidiana cinética

Referencias

1. Basch, Julien (1999). Estructuras de datos cinéticos (Tesis). Universidad de Stanford.
2. Guibas, Leonidas J. (2001), "Estructuras de datos cinéticos" (PDF) , en Mehta, Dinesh P.; Sahni, Sartaj (eds.), Manual de estructuras de datos y aplicaciones , Chapman y Hall/CRC, págs. 23-1–23-18, ISBN 978-1-58488-435-4
3. Abam, Mohammad Ali (2007). Nuevas estructuras de datos y algoritmos para datos móviles (tesis). Universidad Tecnológica de Eindhoven.
4. Rahmati, Zahed (2014). Estructuras de datos cinéticos simples y más rápidas (Tesis). Universidad de Victoria. hdl :1828/5627.
5. Guibas, Leonidas J. (1998), "Estructuras de datos cinéticos: un informe de última generación" (PDF) , en Agarwal, Pankaj K.; Kavraki, Lydia E.; Mason, Matthew T. (eds.), Robótica: la perspectiva algorítmica (Actas del tercer taller sobre los fundamentos algorítmicos de la robótica) , AK Peters/CRC Press, págs. 191–209, ISBN 978-1-56881-081-2