寻找一个区域，其中包含最大的前K个点的和。

Question

我的问题是：在一个二维空间中有N个点，每个点都有一个正权重。给定一个查询，包括两个实数a、b和一个整数k，在平行于坐标轴的边缘上找到大小为a x b的矩形的位置，以使被矩形覆盖的前k个具有最高权重的点的权重之和最大？

欢迎提出任何建议。

P.S.： 有两个相关的问题已经得到了很好的研究：

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

- Arnold

---

如果我选择覆盖所有点的矩形呢？权重将会被最大化。 - Nyavro

有旋转的矩形？或是与给定一组坐标轴平行的矩形？ - Tom Zych

这可能并不是很有帮助，但根据给定的限制，我认为可以肯定地说，如果我们取任何一个矩形（即使是最优的矩形），我们都可以将其移动（而不会失去任何内部点），使得其中一个垂直和水平边缘位于1个或多个点上。也许这种方法可以用于某些算法，比如扫描算法。 - Piotr Pytlik

@PiotrPytlik 扫描矩形是寻找最优矩形的详尽方法，但效率非常低。在最大区域和问题中，解决方案是扫描水平线，而不是矩形，这更有效。您可以在论文“寻找最大和最小对象包围矩形和立方体的统一算法”中找到该算法。 - Arnold

@eh9 我不明白。我需要输出最大化。 - Arnold

Answer 1

你可以将这个问题简化为在矩形中找到最右边和最上面的两个点。因此，你可以选择每一对点并计算前k大的权重（根据你所说的是O(log(N)^2+k)）。复杂度：O(N^2*(log(N)^2+k))。

现在，给定两个点，它们可能不构成一个有效的对：它们可能太远或者一个点可能在另一个点的右侧和顶部。因此，在实际操作中，这将会更快。

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

- ElKamina

---

你的想法非常有趣。我会考虑它。对于最大区域和问题，我们可以在题为“寻找最大和最小对象包围矩形和立方体的统一算法”的论文中进行研究。 - Arnold

Answer 2

一个非最优解如下：

1. 生成所有可能的k元组点（它们是N × N-1 × … × N-k+1，因此这是O（N^k），可以通过递归完成）。

2. 通过消除不在a×b矩形中的所有k元组，将此列表过滤掉：在最坏情况下，这是O（k N^k）。

3. 找到具有最大权重的k元组：在最坏情况下，这是O（k N^k-1）。

因此，此算法为O（k N^k）。

改进算法

步骤2可以与步骤1集成，方法是在一组点已经太大时停止分支递归。这不会改变至少需要扫描元素一次的需求，但它可以显着减少数量：考虑所有点都相互分离，超过矩形大小而找不到解决方案的情况，可以在O（N²）中找到。

此外，在第一步中，排列生成器可以通过预先按x或y坐标对点数组进行相应排序，以按顺序返回点。这很有用，因为它让我们能够在前面丢弃更多的可能性。假设数组按y坐标排序，那么返回的k-plet将按y坐标排序。现在，假设我们正在丢弃一个包含y坐标超出最大矩形范围的点的分支，那么我们也可以丢弃所有下一个兄弟分支，因为它们的y坐标将大于等于当前已超出边界的坐标。

这会增加O（n log n）的排序时间，但在许多情况下改进非常显著 - 再次提到，当存在许多异常值时。应选择与最小矩形边相对应的坐标，除以2D场的相应边 - 我的意思是所有点的最大坐标减去最小坐标。

最后，如果所有点都位于a×b矩形内，则算法仍然执行为O（k N k）。如果这是一个具体的可能性，应该进行检查，一个简单的O（N）循环，如果是这样，那么只需返回具有前N个权重的点即可，这也是O（N）。

- Sklivvz

---

感谢您的回答。由于我的数据集很大（约1百万个点），我认为您的解决方案不够高效。另外，如果一个区域包含少于k个点，则其得分是所有点的权重之和。因此总会有一个答案。 - Arnold

@user2210078，我认为如果您提供更多关于您的情况的细节，我们可以改进。k的值是多少？点分布如何（例如，均匀程度如何，但也在多大空间内？a和b的范围是多少？这些都是我们可以利用来使算法更有效的因素。 - Sklivvz

我旨在为任何数据设计一个高效的算法，就像我在帖子中提到的最大区域和的解决方案一样。k可能很小，大约为2、3、5或10。当然，如果我们知道数据的某些特征，例如点分布，我们可以利用它们来改进我们的算法。在这种情况下，您可以考虑一个例子，即我们的数据集是城市、州或整个美国的地点集（餐厅、电影院等），权重是它们从Yelp或Foursquare获得的评分。 - Arnold