c++ - 用于稀疏数据查找的高效数据结构

Question

情况:

给定一些坐标为 (x, y) 的点范围 0 < x < 100,000,000 和 0 < y <100,000,000

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

1. 我使用 vector 来存储坐标并搜索边长 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);
   

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

这是非常低效的。

Q1。在不改变我使用的算法的情况下，我应该使用什么数据结构来提高时间效率？
Q2。这个问题的高效算法？

Answer 1

在 2 个相对边上有点 - 如果没有，您可以将正方形缩小 1，并且仍然包含相同数量的点。这意味着边的可能坐标仅限于输入点的坐标。不过，输入点可能不在拐角处。 (对于最小矩形，所有 4 个边上都会有点，因为您可以缩小一个维度而不改变另一个维度)

接下来要实现的是每个点将平面分成 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) 排序。