在一个区域中找到权重最大的点

Question

在一个区域中找到权重最大的点

algorithmgeometry

3

我的问题是：

在2D空间中有一组N个点，每个点都有一个权重。给定任何矩形区域R，如何有效地返回该区域内具有最大权重的点？

需要注意的是，所有查询区域R的形状相同，即具有相同的长度和宽度。点和矩形坐标为浮点数。

我的初始想法是使用R树来存储点。对于一个区域R，提取所有在R中的点，然后找到具有最大权重的点。时间复杂度为O(logN+V)，其中V是R中的点数。我们能做得更好吗？

我尝试搜索解决方案，但仍未成功。有什么建议吗？

谢谢，

- Arnold

也许使用四叉树会有帮助？ - Peter de Rivaz

1

如果R内的点的权重是随机分布的，那么您必须检查矩形内的每个点。顺便问一下，您需要一个检查算法还是实现？SO主要是一个编码资源。 - Tim Biegeleisen

你尝试过什么样的搜索？我认为“扫描线”算法可能适用于这里。 - bro

5个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Answer 1

提示：

每个点都有一个“影响区域”，它是该点（左上角）矩形位置的轨迹，使得该点占主导地位。影响区域的集合定义了平面的一个分区。分区的每条边出现在给定点的横坐标[纵坐标]或其横坐标[纵坐标]减去查询区域的宽度[高度]。

如果将坐标值映射到它们的排名（通过对两个轴进行排序），则可以将分区表示为大小为4N²的数字图像。要预先计算此图像，请用负无穷大初始化它，并为每个点填充其权重的影响区域，取最大值。如果查询窗口大小平均为R²像素，则构建图像的成本为NR²。

通过查找相关像素的行和列并返回像素值来进行查询。这需要两个二分搜索，时间复杂度为Lg(N)。

这种方法仅适用于中等规模的N值（例如不超过1000）。通过研究分区图的几何学，可以更好地理解这个问题。

- Micromega · Answer 2

当从欧几里得距离中减去正权重时，您可以尝试加权的Voronoi图。具有大权重的站点倾向于具有附近小权重站点的大单元格。然后按站点数量对单元格进行排序，并为每个单元格计算最小边界框。将其与矩形搜索框匹配。

- IVlad · Answer 3

这听起来像是一个二维区间最大值查询问题。你可以在这里找到一些非常好的算法。

更简单的方法是使用一个二维线段树。

基本上，你的每个线段树节点将存储2D区域而不是1D区间。因此，每个节点将有4个子节点，缩小为四叉树，然后您可以像操作经典线段树一样对其进行操作。这在这里有详细描述。

每次查询的时间复杂度为O(log n)，其中n是点的总数。它还允许您执行更多的操作，例如更新点的权重、更新区域的权重等。

- dpmcmlxxvi · Answer 4

如何在每个树节点中添加一个额外的属性，该属性包含其任何子节点所包含的所有点的最大权重。

在添加点时，这将很容易更新。但是，在删除更改最大值的点时，需要向后遍历树并更新所有父节点的最大值，这需要一些工作来维护。

有了这个属性，如果您想检索具有最大权重的点，则在使用查询区域查询树时，只需遍历具有最大权重的子节点即可。请注意，您可能有多个具有相同最大权重的点，因此您可能需要检查多个子节点。

仅检查具有最大权重属性的子节点将提高查询吞吐量，但会以更多的内存和较慢的构建/修改树的时间为代价。

- user2566092 · Answer 5

请查找所谓的范围树，这在您的情况下需要在二维中实现。这将是一个两层的“树形结构”，其中您首先基于x坐标拆分点集，然后对于结果树中一个节点处的一组x点，您为该节点中的那些点基于y坐标构建一棵树。您可以查找如何调整2-d范围树以在O（（log n）^ 2）时间内返回查询矩形中的点数，而与点数无关。同样，您可以在范围树中存储子矩形中点的计数，也可以存储该矩形内点的最大目标值。这将为您提供O（n log n）时间保证存储和构建时间，并且无论查询矩形中的点数如何，都将提供O（（log n）^ 2）查询时间。

所谓的“分数级联”适应范围树“查找查询矩形中的所有点”的甚至可以将查询时间降至O（log n），但由于您正在取查询矩形内点的值的最大值，因此我不确定。