Structure de données cinétique

Une structure de données cinétique est une structure de données utilisée pour suivre un attribut d'un ensemble géométrique en mouvement continu. Par exemple, une structure de données d'enveloppe convexe cinétique maintient l'enveloppe convexe d'un groupe de $n$ points en mouvement. Le développement de structures de données cinétiques a été motivé par des problèmes de géométrie algorithmique impliquant des solides physiques en mouvement continu, tels que la détection de collision ou le calcul d'occlusion en robotique, en animation ou en infographie.

Aperçu

Les structures de données cinétiques sont utilisées sur des systèmes où il existe un ensemble de valeurs qui changent en fonction du temps, de manière connue et calculable. Donc, les valeurs du système sont des fonctions du temps $v=f(t)$ . Les structures de données cinétiques permettent des requêtes sur un système pour n'importe quelle valeur du temps $t$, et deux opérations supplémentaires :

• ${\textrm {advance}}(t)$ : Avance le système au temps $t$ .
• ${\textrm {change}}(v,f(t))$ : Modifie la trajectoire de la valeur $v$ à $f(t)$, à partir de l'instant courant.

Des opérations supplémentaires peuvent être prises en charge. Par exemple, les structures de données cinétiques sont souvent utilisées sur des nuages de points. Dans ce cas, la structure permet également d'insérer et de supprimer des points.

Contraste avec les structures de données traditionnelles

Une structure de données kinétiques permet aux valeurs qui y sont stockées d'évoluer continuellement suivant le temps. En principe, cette évolution peut être approximée en échantillonnant la position des points à des intervalles de temps fixes, et en supprimant et en réinsérant chaque point dans une structure de données "statique" (traditionnelle). Cependant, une telle approche peut entrainer des problèmes de suréchantillonnage ou de sous-échantillonnage, suivant que le pas de temps choisi est trop petit ou trop grand, ce qui engendre des baisses de performances ou des problèmes de précision.

Approche par certificat

L'approche générale suivante peut être utilisée pour construire des structures de données cinétiques :

1. Initialiser une structure de données qui stocke les informations du système à l'instant $t$ . Cette structure de données permet des requêtes sur le système au temps courant.
2. Ajouter à la structure des données avec des certificats. Les certificats sont des conditions qui permettent d'affirmer que les données de la structure sont exactes. Tant que les certificats restent vrais, les informations de la structure sont fiables.
3. Calculez le temps d'échec de chaque certificat, le moment où il cessera d'être vrai.
4. Stockez les certificats dans une queue de priorité, en fonction de leurs instants d'échec
5. Pour avancer dans le temps $t$, il suffit de déterminer le certificat ayant l'instant d'échec le plus proche à partir de la queue de priorité. Si le certificat échoue avant l'heure $t$, il faut le sortir de la queue de priorité, et mettre a jour la structure des données afin qu'elle soit fiable au moment de l'échec, et mettez à jour les autres certificats. L'opération est a répéter jusqu'à ce que le certificat avec le temps d'échec le plus proche dans la file d'attente prioritaire atteigne le temps $t$ . Si le certificat avec le temps d'échec le plus bas dans la file d'attente prioritaire échoue avec le temps $t$, alors tous les certificats sont vrais à la fois $t$ afin que la structure de données puisse répondre correctement aux requêtes au temps $t$ .

Types d'événements

Les échecs de certificat sont appelés «événements». Un événement est considéré comme interne si la propriété portée par la structure de données kinétique ne change pas lorsque l'événement se produit. Un événement est considéré comme externe si la propriété gérée par la structure de données change lorsque l'événement se produit.

Performance

Avec l'approche utilisant des certificats, il existe quatre mesures de la performance possibles. On dit qu'une quantité est petite si c'est une fonction polylogarithmique de $n$, ou encore si elle est en $O(n^{\epsilon })$ pour $\epsilon$ arbitrairement petit, où $n$ est le nombre d'objets:

Réactivité

La réactivité est le temps maximal nécessaire pour mettre a jour la structure des données et mettre a jour les certificats en cas d'échec d'un des certificats. Une structure de données cinétique est dite réactive si le temps le plus défavorable requis pour une mise à jour est bas.

Localité

Il s'agit du plus grand nombre de certificats dans lequel une valeur est impliquée. Pour les structures impliquant des points mobiles, il s'agit du nombre maximum de certificats dans lequel un arbitraire point est impliqué. Une structure de données cinétique est locale si le nombre maximum de certificats dont une valeur est impliquée est petit.

Compacité

Il s'agit du nombre maximum de certificats utilisés pour mettre a jour la structure de données à tout moment. Une structure de données cinétique est compacte si le nombre de certificats qu'elle utilise est $O(n\operatorname {polylog} n)$ ou $O(n^{1+\epsilon })$ pour $\epsilon$ arbitrairement petit . (un petit facteur de plus que l'espace linéaire)

Efficacité

Le ratio entre le pire concernant les d'événements pouvant survenir à la structure lorsque t tend vers $t=\infty$ par rapport au pire des cas des "modifications nécessaires" à la structure de données. La définition des «changements nécessaires» dépend du problème. Par exemple, dans le cas d'une structure de données cinétiques conservant l'enveloppe cinétique d'un ensemble de points en mouvement, le nombre de changements nécessaires serait déterminé par le nombre de fois ou l'enveloppe cinétique est modifiée au fur et à mesure que le temps avance vers $t=\infty$ . Une structure de données cinétique est dite efficace si ce rapport est petit.

Types de trajectoires

Les performances d'une structure de données cinétiques peuvent être analysées pour certains types de trajectoires. En règle générale, les types de trajectoires suivants sont considérés :

• Affine : (fonctions linéaires)$f(t)=at+b$
• Algébrique de degré borné : (Fonctions polynomiales de degré borné)$f(t)=\sum _{i=0}^{n}a_{i}t^{i}$ pour certains fixes $n$ .
• Pseudo-algébrique : trajectoires telles que tout certificat d'intérêt bascule entre vrai et faux$O(1)$ fois.

Exemples

• Tournoi cinétique
• Liste triée cinétique
• Tas cinétique
• Coque cinétique convexe
• Paire cinétique la plus proche
• Arbre couvrant minimum cinétique
• Arbre couvrant minimum euclidien cinétique