algorithm - 高效查找二维中某个点支配的所有点

Question

在 OCW Advanced Data Structures course ，E. Demaine 教授提到了一种数据结构，能够使用 O(n) 空间找到查询点 (b₂, b₃) 主导的所有点时间复杂度为 O(k)，前提是已完成对点 b₃ 的搜索，其中 k 是输出的大小。

解决方案的工作原理是将上述问题转化为射线刺穿问题，并使用类似于分数级联的技术，如下所示image from the lecture notes :

虽然这个概念本身很直观，但实现实际的数据结构却一点也不简单。

Chazelle 在一篇论文中将此描述为 Filtering Search (pp712) .

我想找到描述和解释此数据结构和算法的其他文献或答案(可能使用伪代码和更多图像，重点关注实现)。

此外，我还想了解更多有关此结构是否可以以非“静态”的方式实现的信息。也就是说，我希望能够尽可能高效地从结构中插入和删除点。

Answer 1

这本书"Computational Geometry: Algorithms and Applications"涵盖此类问题的数据结构。每一章都有一个很好的部分描述了在哪里可以学到更多，包括用于回答本书中未涵盖的相同问题的更复杂的结构。图表足够多，但伪代码不多。

许多这样的结构可以使用“动态数据结构的设计”一书中讨论的技术进行动态化。 Jeff Erickson has some nice notes on the topic.使用分数级联的讨论是Cache-Oblivious Streaming B-trees" - 请参阅有关“忽略缓存的先行数组”的部分。