想象有一个2D空间，在这个空间中有以不同恒定速率生长的圆。存储这些圆的有效数据结构是什么，这样我就可以查询"哪些圆在时间t与点p相交？"。
编辑：我确实意识到，我可以将圆的初始状态存储在空间数据结构中，并在点p与半径为fastest_growth * t的圆相交时进行查询，但当有几个圆生长得非常快，而大多数圆生长得很慢时，这是无效的。
附加编辑：我可以通过将圆圈拆分并按增长率分组来进一步增强上述方法，然后将上述方法应用于每组，但这需要有限的时间才能有效。
将圆表示为3d中的圆锥体，其中第三个维度是时间。然后使用BSP树对它们进行最佳分区。
一般来说，我认为测试相交的最坏情况总是O（n），其中n是圆的数量。大多数空间数据结构都是通过巧妙地划分空间来工作的，这样每一半都有一小部分对象（希望接近一半）。然而，如果对象重叠，那么分区就不可能是完美的；总会有多个对象位于分区中的情况。如果你只考虑两个圆重叠的情况，就没有办法画一条线，这样一个圆完全在一边，另一个圆也完全在另一边。从逻辑的极端来看，假设圆和任意半径的任意位置，就没有办法对它们进行划分，从而使相交测试需要O（log（n））。
这并不意味着，在实践中，您不会从使用树中获得很大的优势，但您获得的优势将取决于圆的配置和查询的分布。
这是我大约一周前发布的另一个问题的简化版本：如何找到光线与移动圆的第一个交点
我还没有时间描述预期的解决方案，但我将尝试在这里概述它（对于这个简单的案例）。
解决这个问题的方法是使用动力学KD树。如果你不熟悉KD树，最好先读一下它们。您还需要添加时间作为附加坐标（使空间为3d而不是2d）。我还没有实施这个想法，但我相信这是正确的做法。
很抱歉，这还没有完全考虑清楚，但看起来你可能会研究乘法加权Voronoi图（MWVD）。看起来对手可能会迫使你用一系列位置合适的查询来计算一个，所以我觉得他们为你的问题提供了一个下限。
假设您根据输入数据计算MWVD。然后，对于查询，将返回与查询点"最近"的圆。然后，您可以确定此圆在查询时是否真的包含查询点。如果没有，那么你就完了：没有一个圆包含你的点。如果是，那么您应该在没有该生成器的情况下计算MWVD，并运行相同的查询。你可能可以从旧的MWVD中计算出新的MWVD：必须填充包含被删除的生成器的单元格，而且似乎（尽管我没有证明）唯一可以填充它的生成器是它的邻居。
某种空间索引，如四叉树或BSP，将为您提供O（log（n））访问时间。
例如，四叉树中的每个节点都可以包含指向与其相交的所有圆的指针的链表
顺便问一下，绕了多少圈？对于小n，您还可以对它们进行迭代。如果你必须不断更新你的空间索引并跳过所有缓存行，那么暴力可能会更快。
你的圆心是如何分布的？如果它们相当均匀地覆盖平面，则可以离散空间和时间，然后执行以下预处理步骤：
for (t=0; t < max_t; t++)
foreach circle c, with centre and radius (x,y,r) at time t
for (int X = x-r; X < x+r; x++)
for (int Y = x-r; Y < y+r; y++)
circles_at[X][Y][T].push_back (&c)
（当然，假设你沿着整数边界、比例和偏移量离散空间和时间，你可以稍后添加圆圈，或者通过推迟计算t的遥远值来摊销成本）
然后，您在时间（t）对点（x，y）的查询可以在circles_at[x][y][ceil(t)] 上进行强力线性检查
权衡是显而易见的，增加三个维度中任何一个的分辨率都会增加预处理时间，但在circles_at[x][y][t]中会给您一个较小的测试桶。
人们会对要使用的空间索引类型提出很多建议，但我想提供一些正交建议。
我认为你最好根据时间建立几个指数，即t_0<t_1<t_2。。。
如果一个点在t_i处与一个圆相交，它也将在t_{i+1}处与它相交。如果事先知道该点，则可以在t_{i+1}及以后的所有计算中消除与t_i处的点相交的所有圆。
如果你事先不知道时间点，那么你可以保留这些时间点树（根据给定时间每个圆圈的大小构建）。在查询时间（例如t_query），找到i使得t_{i-1}<t_query<=t_i。如果你在t_i检查所有可能的圆，你就不会有任何假阴性。
这有点像是对"时间动态感知"的数据结构的黑客攻击，但我不知道。如果你有一个线程环境，那么你只需要维护一个空间索引，并在后台处理下一个索引。为了能够以低延迟响应查询，它将花费大量计算。该解至少应与O（n）解进行比较（遍历每个点并检查dist（point，circl.center）<circl.radius）.
您可以在它们的边界框上进行测试，以筛选出不包含该点的边界框，而不是考虑这些圆。如果你的边界框边都是排序的，这基本上是四个二进制搜索。
棘手的部分是重建任何给定时间（t）的排序边。要做到这一点，您可以从原始点开始：两个列表分别用于x坐标的左侧和右侧，以及两个列表用于y坐标的顶部和底部。对于大于0的任何时间，所有左侧点都将向左移动，等等。您只需要检查其旁边位置的每个位置，就可以获得交换元素和元素旁边位置的点。这将为您提供一个时间点列表，以便修改您的排序列表。如果您现在按时间对这些修改记录进行排序，那么对于任何给定的开始时间和结束时间，您都可以提取两者之间的所有修改记录，并将它们按顺序应用于您的四个列表。我还没有完全弄清楚算法，但我认为会有三个或更多连续元素可以完全在同一时间点交叉的边缘情况，所以你可能需要修改算法来处理这些边缘情况。也许一个包含列表中的位置和要重新排序的记录数的列表修改记录就足够了。
我认为可以创建一个二进制树来解决这个问题。
每个分支都应该包含一个增长的圆圈、一个用于分区的静态圆圈以及分区圆圈干净分区的最新时间。此外，包含在节点中的增长圆的增长率应始终高于其任何子节点的增长圆。
要执行查询，请获取根节点。首先检查它的成长圈，如果它在查询时包含查询点，则将其添加到答案集中。然后，如果查询的时间大于分区线断开的时间，则查询两个子节点，否则，如果点位于分区圆内，则查询左侧节点，否则查询右侧节点。
我还没有完全完成执行插入的细节（困难的部分是更新分区圆，使内部和外部的节点数量大致相等，并最大限度地延长分区断开的时间）。
为了解决少数几个生长速度快的圆圈的问题，您可以按生长速度降序对圆圈进行排序，并检查k个生长速度最快的种植者中的每一个。为了在给定t的情况下找到合适的k，我认为你可以执行二进制搜索来找到索引k，这样k*m=（t*k的增长率）^2，其中m是一个常数因子，你需要通过实验来找到。将平衡随k线性增长的部分与随增长率二次下降的部分。
如果如前所述，在3d中用垂直圆锥体表示生长的圆，则可以将空间划分为填充垂直圆柱体的规则（可能是六边形）网格。对于每个圆柱体，计算与所有圆锥体相交的最小和最大高度（次数）。如果圆心（圆锥体的顶点）位于圆柱体内部，则最短时间为零。然后以最短的相交时间对圆锥体进行排序。作为这种索引的结果，对于每个圆柱体，您将拥有具有3个值的有序记录序列：最小时间、最大时间和圈数。
当你检查三维空间中的某个点时，你取它所属的圆柱体并迭代它的序列，直到存储的最小时间超过给定点的时间。所有得到的锥，其最大时间也小于给定时间，都保证包含给定点。只有给定时间介于最小和最大相交时间之间的圆锥体才需要重新计算。
在索引和运行时间成本之间存在一个经典的权衡——圆柱体直径越小，相交时间的范围就越小，因此在每个点需要重新计算的圆锥体就越少，但必须索引更多的圆柱体。如果圆心分布不均匀，那么搜索比规则网格更好的圆柱体放置配置可能是值得的。
附言：我在这里的第一个答案——刚刚注册发布。希望不会晚。