2D Fractional Cascading on Axis-aligned Planar Subdivisions

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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{|π|(log n)^1/2,α(n)|π|(log n)^1/2}) 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+|π|(log n)^1/2) and this bound is once again tight in both cases.
Original languageEnglish
Title of host publication61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Number of pages22
PublisherIEEE Computer Society
Publication year2021
Publication statusPublished - 2021
Event61st Annual IEEE Symposium on Foundations of Computer Science - Durham, United States
Duration: 16 Nov 202019 Nov 2020


Conference61st Annual IEEE Symposium on Foundations of Computer Science
LandUnited States

See relations at Aarhus University Citationformats

ID: 207955723