在2D空间中生长圆的有效表示？

Question

想象一下,有一个2D空间,在这个空间中,有些圆圈以不同的恒定速率生长.什么是用于存储这些圆的有效数据结构,这样我可以查询"哪些圆与p时间点相交t？".

编辑:我确实意识到我可以在空间数据结构中存储圆的初始状态并进行查询,其中我在p半径为的点处与圆相交fastest_growth * t,但是当有少量圆增长时这不是有效的非常快,而大多数生长缓慢.

附加编辑:我可以通过分割圆圈并按增长率对它们进行分组,然后将上述方法应用于每个组来进一步增强上述方法,但这需要有限的时间才能有效.

Answer 1

某种空间索引，例如四叉树或BSP，将为您提供 O(log(n)) 访问时间。

例如，四叉树中的每个节点都可以包含指向与其相交的所有圆的指针的链接列表。

顺便问一下，有多少圈？对于较小的 n，您也可以迭代它们。如果您经常需要更新空间索引并跳过所有缓存行，那么暴力破解它可能会更快。