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 cinético convexo mantiene el casco convexo de un grupo depuntos móviles. 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 detección de colisión o visibilidad en robótica, animación o gráficos por computadora.
Descripción general
Las estructuras de datos cinéticas se utilizan en sistemas donde hay un conjunto de valores que están cambiando en función del tiempo, de una manera conocida. Entonces el sistema tiene algunos valores, y para cada valor, Se sabe que . Las estructuras de datos cinéticos permiten consultas en un sistema en el tiempo virtual actualy dos operaciones adicionales:
- : Avanza el sistema a tiempo .
- : Altera la trayectoria del valor a , a partir de la hora actual.
Es posible que se admitan operaciones adicionales. Por ejemplo, las estructuras de datos cinéticas se utilizan a menudo 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 volviendo a insertar cada punto en una estructura de datos "estática" (tradicional). Sin embargo, este enfoque es vulnerable al sobremuestreo o al submuestreo, según el intervalo de tiempo que se utilice, y también puede ser un desperdicio de recursos computacionales.
Enfoque de certificados
El siguiente enfoque general se puede utilizar para construir estructuras de datos cinéticos: [5]
- Almacenar una estructura de datos en el sistema en el momento actual . Esta estructura de datos permite realizar consultas sobre el sistema en el tiempo virtual actual.
- Aumente la estructura de datos con certificados. Los certificados son condiciones bajo las cuales la estructura de datos es precisa. Los certificados son todos verdaderos ahora, y la estructura de datos solo dejará de ser precisa cuando uno de los certificados deje de ser cierto.
- Calcule el tiempo de falla de cada certificado, el momento en que dejará de ser cierto.
- Almacene los certificados en una cola de prioridad, codificada por sus tiempos de falla.
- Para avanzar al tiempo , observe 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 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 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 el momento para que la estructura de datos pueda responder correctamente a las consultas en el momento .
Tipos de eventos
Los fallos de certificados se denominan "eventos". Un evento se considera interno si la propiedad mantenida por la estructura de datos cinéticos 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, hay cuatro medidas de rendimiento. Decimos que una cantidad es pequeña si es una función polilogarítmica deo es para arbitrariamente pequeño , dónde es el número de objetos:
Sensibilidad
La capacidad de respuesta es la cantidad de tiempo que se requiere en el peor de los casos para corregir la estructura de datos y aumentar los certificados cuando falla un certificado. Una estructura de datos cinética responde si la cantidad de tiempo que se requiere en el peor de los casos para una actualización es pequeña.
Localidad
El número máximo de certificados en los que está involucrado un valor. Para estructuras que involucran puntos móviles, este es el número máximo de certificados en los que está involucrado un punto. Una estructura de datos cinética es local si el número máximo de certificados con los que está involucrado un valor es 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 o para arbitrariamente pequeño . (un pequeño factor más que el espacio lineal)
Eficiencia
La razón del número de eventos más desfavorables que pueden ocurrir cuando la estructura avanza a al número de casos más desfavorables de "cambios necesarios" 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 el casco cinético de un conjunto de puntos móviles, el número de cambios necesarios sería el número de veces que cambia el casco cinético a medida que se avanza el tiempo.. Se dice que una estructura de datos cinética es eficiente si esta relación es pequeña.
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:
- Affine : (funciones lineales)
- Algebraica de grado acotado: (Funciones polinomiales de grado acotado) para algunos arreglados .
- Pseudo-algebraica : Trayectorias tales que cualquier certificado de interés cambia entre verdadero y falso. veces.
Ejemplos de
Referencias
- ^ Basch, Julien (1999). Estructuras de datos cinéticos (tesis). Universidad Stanford.
- ^ 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
- ^ Abam, Mohammad Ali (2007). Nuevas estructuras de datos y algoritmos para datos móviles (tesis). Universidad Tecnológica de Eindhoven.
- ^ Rahmati, Zahed (2014). Estructuras de datos cinéticas simples y más rápidas (tesis). Universidad de Victoria. hdl : 1828/5627 .
- ^ Guibas, Leonidas J. (1998), "Estructuras de datos cinéticos: un informe de estado del arte" (PDF) , en Agarwal, Pankaj K .; Kavraki, Lydia E .; Mason, Matthew T. (eds.), Robotics: The Algorithmic Perspective (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