论文标题
GPU Voronoi图表的随机移动种子
GPU Voronoi Diagrams for Random Moving Seeds
论文作者
论文摘要
Voronoi图是一种几何结构，在邻近性是一个相关方面的科学或技术应用中广泛使用，它也类似于自然现象，例如蜂窝库，岩层或蜂巢等。通常，计算Voronoi图是在静态上下文中完成的，即输入种子的位置一次定义，并且不会更改。在这项工作中，我们研究了种子移动的动态情况，这会导致动态伏诺曲图随时间变化。特别是，我们考虑均匀的随机移动种子，为此，我们建议\ textIt {动态跳洪算法}（DJFA），这是JFA的变体，它使用的迭代率少于标准JFA。一项实验评估表明，DJFA的速度高达$ \ sim 5.3 \ times $以上，同时保持至少$ 88 \％$，并且在许多情况下保持接近$ 100 \％$。这些结果朝着实现基于GPU的动态伏诺图的实时计算而迈出了一步。
The Voronoi Diagram is a geometrical structure that is widely used in scientific or technological applications where proximity is a relevant aspect to consider, and it also resembles natural phenomena such as cellular banks, rock formations or bee hives, among others. Typically, computing the Voronoi Diagram is done in a static context, that is, the location of the input seeds is defined once and does not change. In this work we study the dynamic case where seeds move, which leads to a dynamic Voronoi Diagram that changes over time. In particular, we consider uniform random moving seeds, for which we propose the \textit{dynamic Jump Flooding Algorithm} (dJFA), a variant of JFA that uses less iterations than the standard JFA. An experimental evaluation shows that dJFA achieves a speedup of up to $\sim 5.3 \times$ over JFA, while maintaining a similarity of at least $88\%$ and close to $100\%$ in many cases. These results contribute with a step towards the achievement of real-time GPU-based computation of dynamic Voronoi diagrams for any particle simulation.
