我在最近邻搜索附近有一个问题，但不完全是。
对于二维空间中的给定矩形区域（与轴对齐），我需要找到属于该区域的所有点。我可以提前准备任何关于我的积分的数据。我对点坐标有限制（假设我们拥有的所有点都在 X 和 Y 坐标的 0 到 1 区域内）。
查询数（区域）>>点数。因此，我的优先事项是：
哪些算法适合这里？（我会很高兴有一些关于该主题的书籍或文章）。
例子：
我有一个点坐标数组，范围从 0 到 1：
{0.1224,0.2345}，{0.01,0.99}，{0.94,0.5}
并获取查询以查找 X 中从 0.1 到 0.2 以及 Y 中从 0.2 到 0.4 的区域中的所有点。
然后我需要找到第一个点 {0.1224,0.2345}。
听起来你有一些比赛条件。目前还不清楚你是如何做到的。通常的方法是让准备工作单线程，冻结结构（将其作为 const 到处传递），然后所有查询可以并行运行而无需协调，因为结构是不可变的。
另一种方法是使用 KD 树或四叉树。您可能会遇到与您现在看到的相同的种族问题。但是如果您想尝试一下，请使用随机点，或者如果您有能力为拆分选择最佳点（但在实践中应该不重要）。你会有一些类似于 O(logNP + R) 的东西，其中 R 是结果中的点数。
http://en.wikipedia.org/wiki/Kd_tree http://en.wikipedia.org/wiki/Quadtree
分别根据 x 轴和 y 轴对点进行排序。
获取与相应轴的限制匹配的 x 和 y 的子集。
选择范围内元素较少的那个。对于范围内的所有元素，选择落在另一个轴范围内的元素。
准备时间 nlogn。
搜索时间：最坏情况 n，但实际上远少于此。
此外，您可以根据您可以拥有的内存量来确定搜索时间 (logn)^2 或 logn。
如果您有 O(n^2) 内存，则可以根据 y 值对 x 值的每个范围内的数字进行排序。在进行搜索时，您必须先找到 x 上的范围，然后在与该范围相对应的排序列表中进行搜索。
或者，您可以在 x 轴排序列表上对长度为 2、4、8.. 等的非重叠范围进行排序。当您获得 ax 范围时，您必须在共同构成范围的迷你排序范围（最坏的情况下，logn 范围）内进行搜索（每次搜索最多花费 logn 时间）。实际上搜索时间是 (logn)^2。
正如@Sorin 建议的那样，您最好使用几何树，例如 KD-tree 或 R-tree。准备好结构后，它保持不变，您可以从不同的线程并行查询它（当然，我假设结构的实现方式不会在查询期间改变其状态）。
许多库都提供此类数据，例如 Boost.Geometry 有 rtree，OpenCV 有 KDtree，详见https://stackoverflow.com/questions/1402014/kdtree-implementation-c。
至于数据准备，典型的方法是递归的，并且非常适合树结构：将数据分成两半（例如，X 坐标高于某个枢轴的那些和低于某个枢轴的那些），递归地为每个部分构建一棵树，合并）。
递归调用可以分配给单独的线程。事实上，完全符合tbb::parallel_reduce和相似的平行模式。在回答这个问题时，我发现了一些逐字逐句遵循该计划的论文。