高效稀疏数据查找的数据结构

Question

情况：

给定一些坐标为（x，y）的点，范围为0 < x < 100,000,000和0 < y < 100,000,000。

我必须找到最小的正方形，其中至少包含N个点在其边缘和内部。

1. 我使用向量存储坐标，并搜索所有边长为minLength到maxLength的正方形（在相关空间中应用暴力方法）

struct Point
{
        int x;
        int y;
};

vector<Point> P;
int minLength = sqrt(N) - 1;
int maxLength = 0;

//   bigx= largest x coordinate of any point
//   bigy= largest y coordinate of any point
//   smallx= smallest x coordinate of any point
//   smally= smallest y coordinate of any point

(bigx - smallx) < (bigy - smally) ? maxLength = (bigx - smallx) : maxLength = (bigy - smally);

对于每个正方形，我查找并遍历完整的向量以查看其边缘和内部是否至少有N个点。

这种方法非常耗时。

Q1. 我应该使用哪种数据结构来提高时间效率而不改变我使用的算法？
Q2. 解决此问题的有效算法？

- NightFurry

---

有趣的问题。我在想这个问题是否是NP难问题。 - NPE

在“n（或k）最近邻居”问题中，使用均匀范数作为距离度量，您可能会发现一些有用的思路。 - Angew is no longer proud of SO

@NPE：一点也不。输入域可以排序，事实证明这是最困难的部分。从那里开始就是花式计数。 - MSalters

NPE：当然不是，很明显有一个多项式时间算法：给定一个解方案正方形，我们可以在仍包含相同点的情况下缩小它，直到其中三条边包含集合中的一个点。因此通过考虑所有的3点子集，我们可以找到这个正方形。 - Niklas B.

这篇论文介绍了一个时间复杂度为 O(n log n + kn log^2 k) 的算法来解决该问题，其中n是点的数量，k是必须在正方形内的点的数量。链接 - Niklas B.

Answer 1

有两个对立的边上有点 - 如果没有，你可以将正方形缩小1并仍然包含相同数量的点。这意味着边缘的可能坐标受限于输入点的坐标。然而，输入点可能不在角落上。（对于最小矩形而言，四条边上都会有点，因为可以缩小一个维度而不改变另一个维度。）

下一步要理解的是，每个点将平面分成4个象限，每个象限包含一些点。（这些点数可能超过总点数，因为象限之间存在一个像素的重叠区域）。假设NW(p)是位于点p的西北方向的点的数量，即那些具有x>=px且y>=py的点数。那么正方形中的点数为NW(bottomleft) + NW(topright) - NW(bottomright) - NW(topleft)。

计算所有输入点的NW(p)相当容易。按x排序，并按相等的x排序y。最西北的点具有NW(p)==0。下一个点如果位于第一个点的东南部，则可以具有NW(p)==1，否则它具有NW(p)==0。在该阶段还保持SW(p)也很有用，因为您正在从西到东处理点，并且它们因此未按南到北排序。计算了NW（p），就可以在O(1)中确定正方形S中的点数。

回想一下，正方形大小受到需要在相对的边上具有点的限制。假设点位于左侧（西侧）和右侧边缘 - 您仍按x顺序对点进行排序。首先假定左侧边缘在最左侧的x坐标处，然后查看右侧边缘必须是什么才能包含N个点。现在将左侧边缘移至下一个x坐标并找到新的右侧边缘（因此也有新的正方形）。重复此操作，直到正方形的右边缘是最右侧的点。

正方形也可能在y方向上被限制。只需按y方向对点进行排序并重复此操作，然后选择两种结果之间的最小正方形。

由于您在线性地遍历点x和y方向，因此该部分仅为O(N)，而主要因素是O(N log N)排序。

- MSalters

---

首先假设左边缘位于最左侧的x坐标处，然后看右边缘必须包含N个点。我认为这并不是微不足道的。正方形中的点数取决于正方形的垂直位置，而不仅仅是它的宽度。此外，我们无法证明正方形中的一个点必须在其角落上，因此我不知道如何执行此步骤。 - Niklas B.

Answer 2

Rtree允许进行空间搜索，但没有stl实现，尽管sqlite可以进行绑定。这可以回答“获取范围内的所有点”、“k个最近邻居”的问题。

寻找具有最密集数据的区域，类似于聚类问题。

迭代遍历点并找到每个点的N个最近条目。然后生成最小圆-中心将是Max(x)-min(x)，Max(y)-min(y)。可以形成一个包含所有邻居的正方形，与圆相比，边长在2r长度和2sqrt(r)长度之间。

构建结构需要O(x)时间 搜索最小簇需要O(X N log(X))时间

- mksteve

Answer 3

请查看http://en.wikipedia.org/wiki/Space_partitioning以获取使用分治技术解决此问题的算法。这绝对可以在多项式时间内解决。

---

另一种算法的变体可以按以下方式进行。

• 在点上生成 Voronoi 图以获取邻居信息。[ O(nlog(n)) ]
• 现在使用动态规划，DP 将类似于在 2D 数组中查找最大子数组的问题。这里，您将在其前面保留点数，而不是数字之和。

  2.a 基本上，类似于这样的递归将保持。 [ O(n) ]

从（0,0）到（x，y）正方形中的元素数量=（从正方形（0,0到((x-1)，y))的元素数量+（从正方形0,0到（x，y-1）的元素数量）-（（0,0）-((x-1)，(y-1)))的元素数量

对于其邻域和左侧和上方的所有点，您的递归将需要更改，而不仅仅是上面和左侧的点。

• 一旦DP准备好，您可以在O(1)时间内查询方块中的点。另一个O(n^2)循环用于查找所有可能的组合并找到最小的方块。

• 你甚至可以贪心地从最小的方块开始搜索，这样你就可以在找到合适的方块后立即结束搜索。

---

- Kshitij Banerjee

Answer 4

注意：对于您的第二个问题（可能会带来更大的好处），有许多答案，但我只涉及您的第一个问题，即在不改变算法的情况下使用哪些数据。

因此，我认为您选择使用向量已经相当不错了，因为一般而言，向量提供最佳的负载/开销比和最快的迭代。为了找出具体的瓶颈，请使用分析器，否则您只是在猜测。对于大型向量，有一些需要避免的事情：

- 过度分配，这会浪费空间。 - 不足分配，这会导致在向量增长到必要大小时进行复制。 - 复制。

- Ulrich Eckhardt