Estructura de datos cinética

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

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 casco convexo cinético mantiene el casco convexo de un grupo de 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 colisiones o detección de visibilidad en robótica, animación o gráficos por computadora. ${\displaystyle n}$

Descripción general

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

• ${\displaystyle {\textrm {advance}}(t)}$: Avanza el sistema al 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)}$

Es posible que se admitan operaciones adicionales. Por ejemplo, las estructuras de datos cinéticos se suelen utilizar con un conjunto de puntos. En este caso, la estructura normalmente permite insertar y eliminar 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 aproximar muestreando la posición de los puntos a intervalos de tiempo fijos y eliminando y reinsertando cada punto en una estructura de datos "estática" (tradicional). Sin embargo, este enfoque es vulnerable a un sobremuestreo o un submuestreo, según el intervalo de tiempo utilizado, y también puede suponer un desperdicio de recursos computacionales.

Enfoque de certificados

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

1. Almacenar una estructura de datos en el sistema en el momento actual . Esta estructura de datos permite realizar consultas sobre 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. Todos los certificados son verdaderos ahora y la estructura de datos solo dejará de ser precisa cuando uno de los certificados ya no sea verdadero.
3. Calcula el tiempo de fallo de cada certificado, momento en el que dejará de ser verdadero.
4. Almacene los certificados en una cola de prioridad, codificada por sus tiempos de falla.
5. Para avanzar al tiempo , mire el certificado con el tiempo de falla más bajo de la cola de prioridad. Si el certificado falla antes de tiempo , sáquelo de la cola y corrija la estructura de datos para que sea precisa en el momento del error, 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 un tiempo . Si el certificado con el tiempo de falla más bajo en la cola de prioridad falla después de un tiempo , entonces todos los certificados son verdaderos en ese momento para que la estructura de datos pueda responder correctamente las consultas en ese momento . ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$

tipos de eventos

Los errores de certificado se denominan "eventos". Un evento se considera interno si la propiedad mantenida por la estructura de datos cinética no cambia cuando ocurre el evento. Un evento se considera externo si la propiedad mantenida por la estructura de datos cambia cuando ocurre el evento.

Actuación

Cuando se utiliza el enfoque de certificados, existen cuatro medidas de desempeño. Decimos que una cantidad es pequeña si es una función polilogarítmica de , o es arbitrariamente pequeña , donde es el número de objetos: ${\displaystyle n}$ ${\displaystyle O(n^{\epsilon })}$ ${\displaystyle \epsilon }$ ${\displaystyle n}$

Sensibilidad

La capacidad de respuesta es la cantidad de tiempo necesaria, en el peor de los casos, para arreglar la estructura de datos y aumentar los certificados cuando falla un certificado. Una estructura de datos cinética responde si la cantidad de tiempo requerida para una actualización en el peor de los casos es pequeña.

Localidad

El número máximo de certificados en los que está involucrado cualquier valor. Para estructuras que involucran puntos móviles, este es el número máximo de certificados en los que está involucrado cualquier punto. Una estructura de datos cinética es local si el número máximo de certificados en los que está involucrado cualquier valor es pequeño.

Compacidad

El número máximo de certificados utilizados para aumentar la estructura de datos en cualquier momento. Una estructura de datos cinética es compacta si el número de certificados que utiliza es arbitrariamente pequeño . (un pequeño factor más 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 la estructura avanza 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éticos que mantiene el casco cinético de un conjunto de puntos en movimiento, el número de cambios necesarios sería el número de veces que el casco cinético cambia a medida que avanza el tiempo . 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 se puede analizar para determinados tipos de trayectorias. Normalmente se consideran los siguientes tipos de trayectorias:

• Afines :(Funciones lineales) ${\displaystyle f(t)=at+b}$
• Algebraico de grado acotado : (funciones polinómicas de grado acotado) para algunos fijos . ${\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ética
• montón cinético
• Casco cinético convexo
• Par cinético más cercano
• Árbol de expansión mínimo cinético
• Árbol de expansión mínimo euclidiano cinético

Referencias

1. Basch, Julien (1999). Estructuras de datos cinéticos (Tesis). Universidad Stanford.
2. Guibas, Leonidas J. (2001), "Estructuras de datos cinéticos" (PDF) , en Mehta, Dinesh P.; Sahni, Sartaj (eds.), Manual de estructuras y aplicaciones de datos , 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: informe sobre el estado del arte" (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