Arn*_*old 9 algorithm geometry computational-geometry
我的问题是:我们在2D空间中有N个点,每个点都有一个正重量.给定由两个实数a,b和一个整数k的查询,找到大小AXB的矩形的位置,与边缘平行于轴线,这样的前k个点,即,k个点具有最高权重的总和矩形覆盖的权重最大化？
任何建议表示赞赏.
PS:有两个相关的问题已经得到很好的研究:
您可以将此问题简化为在矩形中查找两个点：最右边和最上面。因此，您可以有效地选择每对点并计算 top-k 权重（根据您的说法是 O(log(N)^2+k)）。复杂度：O(N^2*(log(N)^2+k))。
现在，给定两个点，它们可能无法形成有效的对：它们可能太远，或者一个点可能位于另一个点的右侧和顶部。所以，实际上，这会快得多。
我的猜测是，最佳解决方案将是最大区域和问题的变体。您能指出描述该算法的链接吗？