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

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);
   

2. 对于我查找的每个方格,遍历完整的向量以查看其边缘和内部是否至少有N个点.

这是非常低效的时间.

Q1.我应该使用什么数据结构来提高时间效率而不改变我使用的算法？
Q2.这个问题的有效算法？

Answer 1

请参阅http://en.wikipedia.org/wiki/Space_partitioning了解使用分而治之技术来解决此问题的算法。这绝对可以在多项式时间内解决。

另一种变体算法可以在以下几行中。

• 在点上生成 vornoi 图以获取邻居信息。[ O(nlog(n)) ]

• 现在使用动态规划，DP 将类似于在 2D 数组中查找最大子数组的问题。在这里，您将记录前面的点数，而不是数字的总和。

  2.a 基本上与此类似的递归将成立。[ 在） ]

方格中从 (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) 循环从所有可能的组合中查找并找到最小二乘。

• 你甚至可以贪婪地从最小的方格开始，这样一旦找到合适的方格就可以结束搜索。