动力学数据结构

南宫松

2023-03-14

本文向大家介绍动力学数据结构，包括了动力学数据结构的使用技巧和注意事项，需要的朋友参考一下

基本概念

动力学数据结构被定义为实现为跟踪连续运动的几何系统的属性的数据结构。例如，动力学凸包数据结构跟踪一组n个运动点的凸包。

动力学数据结构的开发受到涉及连续运动的物理对象的计算几何问题的启发，例如机器人技术，动画或计算机图形学中的碰撞或可见性检测。

运动数据结构是在系统上实现的，在该系统中，存在一组值以时间的函数形式以所谓的方式变化。因此，系统具有一些值，并且对于每个系统值v，它表示v = f(t)。运动数据结构允许在当前虚拟时间t上对系统进行查询，并执行两个附加操作

可以支持其他操作。例如，动力学数据结构经常以一组点来实现。在这种情况下，该结构通常允许插入和删除点。

动态数据结构允许存储在其中的值随时间连续变化。原则上，可以通过以固定的时间间隔对点的位置进行采样，然后将每个点删除并将其重新插入“静态”（传统）数据结构中来近似估算。但是，这种方法容易受到过采样或欠采样的影响，具体取决于实现的时间间隔，并且还可能浪费计算资源。

可以采用以下一般方法来建立动力学数据结构

存储当前时间t上系统上的数据结构。此数据结构允许在当前虚拟时间在系统上进行查询。
带有证书的数据结构得到增强。证书被视为数据结构准确的条件。证书现在都是真实的，并且仅当其中一个证书不再真实时，数据结构才会变得完美或准确。
计算每个证书的失败时间，即该证书不再为真的时间。
证书存储在优先级队列中，以其失败时间作为密钥。
要前进到时间t，请从优先级队列中查看具有最小故障时间的证书。如果证书在时间t之前失败，则将其从队列中删除或弹出，并修复数据结构，使其在失败时是完美的或准确的，并更新证书。重复此过程，直到除非在时间t之后优先级队列中失败时间最短的证书失败为止。如果优先级队列中具有最小故障时间的证书在时间t之后失败，则所有证书在时间t都声明为true，因此数据结构可以在时间t正确回答查询。

证书失败称为“事件”。如果动力学数据结构维护的属性在事件发生时没有发生变化，则将事件声明为内部事件。如果由数据结构维护的属性在事件发生时发生更改，则将事件声明为外部事件。

实施证书方法时，有四个绩效衡量指标。如果它是n的对数函数，或者对于随机小€为O（n€），我们称数量小，其中n被视为对象数。