algorithm - 找到具有最大 top-K 点总和的区域

Question

我的问题是:我们在二维空间中有 N 个点，每个点都有一个正权重。给定一个由两个实数 a、b 和一个整数 k 组成的查询，找到一个大小为 a x b 的矩形的位置，其边与轴平行，使得前 k 个点的权重之和，即最高的 k 个点矩形覆盖的权重最大化？

如有任何建议，我们将不胜感激。

附言:有两个相关问题已经得到充分研究:

• 最大区域总和:找到总权重总和最大的矩形。复杂度:NlogN。
• 正交范围的前 K 个查询:在给定的矩形中找到前 k 个点。复杂度:O(log(N)^2+k)。

Answer 1

您可以将此问题简化为找到矩形中的两个点:最右边和最上面。因此，您可以有效地选择每一对点并计算前 k 个权重(根据您的说法是 O(log(N)^2+k))。复杂度:O(N^2*(log(N)^2+k)).

现在，给定两个点，它们可能不会形成有效的一对:它们可能太远或者一个点可能在另一个点的右边和顶部。所以，实际上，这会快得多。

我的猜测是最优解是最大区域和问题的变体。您能否指出描述该算法的链接？