找到具有最大 top-K 点总和的区域
Find a region with maximum sum of top-K points
我的问题是：我们在 2D space 中有 N 个点，每个点都有一个正权重。给定一个由两个实数 a、b 和一个整数 k 组成的查询，找到一个大小为 a x b 的矩形的位置，其边与轴平行，使得前 k 个点的权重之和，即最高的 k 个点矩形覆盖的权重最大化？
如有任何建议，我们将不胜感激。
P.S.:
有两个相关的问题，已经被充分研究过：
- 最大区域和：找到总权重和最大的矩形。复杂度：NlogN.
- top-K 查询正交范围：在给定的矩形中找到 top-k 点。复杂度：O(log(N)^2+k).
non-optimal 答案如下：
生成所有可能的k-plets点（它们是N × N-1 × … × N-k+1，所以这是O(Nk) 并且可以通过递归完成).
通过消除所有未包含在 a×b 矩形中的 k-plets 来过滤此列表：这是一个 O(k Nk ) 在最坏的情况下。
找到权重最大的k-plet：最差也是O(k Nk-1)
因此，这个算法是O(k Nk).
改进算法
当一组点已经太大时，可以通过停止分支递归将步骤 2 集成到步骤 1 中。这不会改变至少扫描一次元素的需要，但它可以显着减少数量：想想没有解决方案的情况，因为所有点的间隔大于矩形的大小，可以在 O( N2).
另外，步骤1中的排列生成器可以return按x或y坐标顺序排列的点，对应pre-sorting点数组。这很有用，因为它可以让我们预先放弃更多的可能性。假设数组按 y 坐标排序，那么 k-plets returned 将按 y 坐标排序。现在，假设我们要丢弃一个分支，因为它包含一个点，其 y 坐标在最大矩形之外，我们也可以丢弃所有下一个兄弟分支，因为它们的 y 坐标将大于等于当前已经超出最大矩形的分支界限。
这为排序增加了 O(n log n)，但在许多情况下改进可能非常显着——同样，当有许多离群值时。坐标应选择对应于最小矩形边除以二维场的对应边——我的意思是最大坐标减去所有点的最小坐标。
最后，如果所有的点都在一个a×b的矩形内，那么算法的执行时间仍然是O(k Nk)。如果这是一个具体的可能性，应该检查它，一个简单的 O(N) 循环，如果是这样，那么它就足以 return 具有前 N 个权重的点，这也是 O(N)。
您可以将此问题简化为找到矩形中的两个点：最右边和最上面。因此，您可以有效地 select 每对点并计算前 k 个权重（根据您的说法是 O(log(N)^2+k)）。复杂度：O(N^2*(log(N)^2+k)).
现在，给定两个点，它们可能不会形成有效的一对：它们可能太远，或者一个点可能在另一个点的右边和顶部。所以，实际上，这会快得多。
我猜最优解是最大区域和问题的变体。你能指出描述该算法的 link 吗？
我的问题是：我们在 2D space 中有 N 个点，每个点都有一个正权重。给定一个由两个实数 a、b 和一个整数 k 组成的查询，找到一个大小为 a x b 的矩形的位置，其边与轴平行，使得前 k 个点的权重之和，即最高的 k 个点矩形覆盖的权重最大化？
如有任何建议，我们将不胜感激。
P.S.: 有两个相关的问题，已经被充分研究过：
- 最大区域和：找到总权重和最大的矩形。复杂度：NlogN.
- top-K 查询正交范围：在给定的矩形中找到 top-k 点。复杂度：O(log(N)^2+k).
non-optimal 答案如下：
生成所有可能的k-plets点（它们是N × N-1 × … × N-k+1，所以这是O(Nk) 并且可以通过递归完成).
通过消除所有未包含在 a×b 矩形中的 k-plets 来过滤此列表：这是一个 O(k Nk ) 在最坏的情况下。
找到权重最大的k-plet：最差也是O(k Nk-1)
因此，这个算法是O(k Nk).
改进算法
当一组点已经太大时，可以通过停止分支递归将步骤 2 集成到步骤 1 中。这不会改变至少扫描一次元素的需要，但它可以显着减少数量：想想没有解决方案的情况，因为所有点的间隔大于矩形的大小，可以在 O( N2).
另外，步骤1中的排列生成器可以return按x或y坐标顺序排列的点，对应pre-sorting点数组。这很有用，因为它可以让我们预先放弃更多的可能性。假设数组按 y 坐标排序，那么 k-plets returned 将按 y 坐标排序。现在，假设我们要丢弃一个分支，因为它包含一个点，其 y 坐标在最大矩形之外，我们也可以丢弃所有下一个兄弟分支，因为它们的 y 坐标将大于等于当前已经超出最大矩形的分支界限。
这为排序增加了 O(n log n)，但在许多情况下改进可能非常显着——同样，当有许多离群值时。坐标应选择对应于最小矩形边除以二维场的对应边——我的意思是最大坐标减去所有点的最小坐标。
最后，如果所有的点都在一个a×b的矩形内，那么算法的执行时间仍然是O(k Nk)。如果这是一个具体的可能性，应该检查它，一个简单的 O(N) 循环，如果是这样，那么它就足以 return 具有前 N 个权重的点，这也是 O(N)。
您可以将此问题简化为找到矩形中的两个点：最右边和最上面。因此，您可以有效地 select 每对点并计算前 k 个权重（根据您的说法是 O(log(N)^2+k)）。复杂度：O(N^2*(log(N)^2+k)).
现在，给定两个点，它们可能不会形成有效的一对：它们可能太远，或者一个点可能在另一个点的右边和顶部。所以，实际上，这会快得多。
我猜最优解是最大区域和问题的变体。你能指出描述该算法的 link 吗？