algorithm - 用于查找大于或小于每个笛卡尔维度中某个值的所有点的空间数据结构

Question

我目前正在研究一个优化问题，该问题需要在所有基本方向上找到大于(或在某些情况下小于)特定点的所有点。例如，在 2D 中，我可能需要找到所有满足条件的点:

x > x* and y < y* 
for an arbitrary point (x*,y*)

(例如，如果下图中的蓝色点是 (x*,y*)，我需要蓝色虚线定义的框中的所有点。

注意:我需要这是一个 N 维结构/搜索，因为我的实际优化问题有超过 2 个必须解决的目标。典型的搜索空间大约有 1000-5000 个点，并且有 2 到 5 个维度。

是否有任何特定的数据结构非常适合这个目的？过去我使用 kd-trees 来寻找最近的邻居，以及半径内的所有点，但是在这种情况下我需要定向搜索。看起来某种形式的 R 树可能会起作用，我的搜索矩形将从 x*、y* 分别变为一些大部分为正值和大部分为负值。是否有针对此类搜索的更好的数据结构？

Answer 1

根据我从你的评论中读到的内容，你得到了一组点 P₁, ..., P_n并且您想为每个点找到 P_i = (x₁, ..., x_d) P_j = (y₁, ..., y_d) 与 的点数x_k R_k y_k 对于所有 k，其中 R _k 是 (<, >) 之一。

一个观察结果是，您可以根据点的第一个坐标对点进行排序，然后按照它们相对于该坐标变得可见的顺序将它们添加到您的数据结构中。这从您的搜索问题中删除了一个维度，因此在 d 维的情况下，您的问题现在减少为 (d-1) 维正交范围查询问题。这种优化完全独立于您实际解决正交范围查询的方式，它本身可能会使暴力实现更加可行。

由于您的点集或多或少是静态的(您可以在完整的点集上构建数据结构，最初将所有节点的计数器设置为零，然后通过启用它们来“插入”点)，您可以使用 range tree解决正交范围查询。在简单的实现中，这为您提供了 O(n log^d-2 n) 预处理和 O(log^d-2 n ) 查询时间，数据结构略有增强版本

因此，一个阶段的总成本将是 O(n log^d-2 n)。由于您的 n 太小了，我不确定这是否真的会给您带来很多好处(对于 5-d 的情况可能不明智，甚至对于 4-d 也可能不明智)。

如果您想走那条路，我强烈推荐 Erik Demaine's data structures lectures ，它涵盖了正交范围查询(在 L03 和 L04 中)。他还介绍了您需要的概念上稍微简单的半开查询，因此也许可以用较低的常数因子来实现。

不幸的是，原始范围树数据结构是完全静态的，但存在动态变体，因此您甚至可以在具有许多共享点的阶段之间重用树，并实际利用具有更好查询时间的变体。您可以搜索“动态正交范围查询”以获取更多信息，有几篇关于该主题的论文。不过，我怀疑这对您的问题规模是否有意义。

如果您的点足够随机分布，您可以将这些点分成 O(n^0.5) 个矩形桶。您可以在 O(1) 中计算一个桶中的点数，在 O(n^0.5) 中计算一个桶中的点数与范围树相比，该实现的开销非常低。结合一个坐标的排序，这应该会给你不错的加速。这绝对是我首先要尝试的。