找出一个顶点之和最大的区域

Question

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

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

P.S.：有两个相关的问题，这些问题已经得到了充分的研究：

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

Answer 1

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

现在，给定两点，它们可能不构成一个有效的对:它们可能太远，或者一个点可能是对的，而另一个点的顶端。因此，在现实中，这将是更快。

我猜想最优解将是最大区域和问题的一个变化。你能指出一个描述该算法的链接吗？