论文标题
轴平面分区的2D分数级联
2D Fractional Cascading on Axis-aligned Planar Subdivisions
论文作者
论文摘要
分数级联是数据结构中的有影响力技术之一，因为它为解决重要的迭代搜索问题提供了一个通用框架。在问题中，输入是一个具有恒定度的图形$ g $，每个顶点的$ g $都有一组值。目标是预处理$ g $，以便在给定查询值$ q $和连接的$ g $ $ g $的连接子图$π$时，我们可以在与$π$的顶点相关的所有集合中找到$ q $的前身。分数级联的基本结果是存在使用线性空间的数据结构，并且可以回答$ o（\ log n + |π|）$时间[Chazelle and Guibas，1986]。尽管在过去的几十年中，这种技术引起了很多关注，但几乎二次的空间下降了“ 2D分数级联” [Chazelle and Liu，2001]，使研究人员确信研究人员认为，分数级联基本上是一项1D技术。 在2D分数级联中，该输入包括每个顶点$ g $的平面细分，查询是一个点$ q $和一个子图$π$，目标是在与$π$的顶点相关的所有细分中找到包含$ q $的单元。在本文中，我们表明，有可能绕过Chazelle和Liu的下限，以进行与轴线对齐的平面细分。我们提出了许多上限和下限，这些上限表明在2D中，问题的结构更丰富。当$ g $是一棵树而$π$是一条路径时，可以在$ o（\ log {n}+| |+|+\ \ \ \ {|π| \ sqrt {\ log {n}}，α（n}}，α（n）（n）（n）（n）\ sqrt {$ log log {逆Ackermann函数；令人惊讶的是，我们显示了该界限的两个分支都紧密，直到逆Ackermann因子。当$ g $是一般图形或$π$是一般子图时，查询键将变为$ o（\ log n + |π| \ sqrt {\ log n}）$，并且在两种情况下，此界限再次紧密。
Fractional cascading is one of the influential techniques in data structures, as it provides a general framework for solving the important iterative search problem. In the problem, the input is a graph $G$ with constant degree and a set of values for every vertex of $G$. The goal is to preprocess $G$ such that when given a query value $q$, and a connected subgraph $π$ of $G$, we can find the predecessor of $q$ in all the sets associated with the vertices of $π$. The fundamental result of fractional cascading is that there exists a data structure that uses linear space and it can answer queries in $O(\log n + |π|)$ time [Chazelle and Guibas, 1986]. While this technique has received plenty of attention in the past decades, an almost quadratic space lower bound for "2D fractional cascading" [Chazelle and Liu, 2001] has convinced the researchers that fractional cascading is fundamentally a 1D technique. In 2D fractional cascading, the input includes a planar subdivision for every vertex of $G$ and the query is a point $q$ and a subgraph $π$ and the goal is to locate the cell containing $q$ in all the subdivisions associated with the vertices of $π$. In this paper, we show that it is possible to circumvent the lower bound of Chazelle and Liu for axis-aligned planar subdivisions. We present a number of upper and lower bounds which reveal that in 2D, the problem has a much richer structure. When $G$ is a tree and $π$ is a path, then queries can be answered in $O(\log{n}+|π|+\min\{|π|\sqrt{\log{n}},α(n)\sqrt{|π|}\log{n}\})$ time using linear space where $α$ is an inverse Ackermann function; surprisingly, we show both branches of this bound are tight, up to the inverse Ackermann factor. When $G$ is a general graph or when $π$ is a general subgraph, then the query bound becomes $O(\log n + |π|\sqrt{\log n})$ and this bound is once again tight in both cases.
