Aarhus University Seal / Aarhus Universitets segl

2D generalization of 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 and important techniques in data structures, as it provides a general framework for solving a common important problem: The iterative search problem. In the problem, the input is a graph G with constant degree. Also as input, we are given a set of values for every vertex of G. The goal is to preprocess G such that when we are given a query value q, and a connected subgraph pi of G, we can find the predecessor of q in all the sets associated with the vertices of pi. The fundamental result of fractional cascading, by Chazelle and Guibas, is that there exists a data structure that uses linear space and it can answer queries in O(log n+ vert pi vert) time, at essentially constant time per predecessor [15]. While this technique has received plenty of attention in the past decades, an almost quadratic space lower bound for'two-dimensional fractional cascading' by Chazelle and Liu in STOC 2001 [17] has convinced the researchers that fractional cascading is fundamentally a one-dimensional technique. In two-dimensional fractional cascading, the input includes a planar subdivision for every vertex of G and the query is a point q and a subgraph pi and the goal is to locate the cell containing q in all the subdivisions associated with the vertices of pi. In this paper, we show that it is actually 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 two-dimensions, the problem has a much richer structure. When G is a tree and pi is a path, then queries can be answered in O(log n+ vert pi vert + min {vert pi vert sqrt{log n},alpha(n) sqrt{vert pi vert} log n }) time using linear space where alpha 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 pi is a general subgraph, then the query bound becomes O(log n+ vert pi vert sqrt{log n}) and this bound is once again tight in both cases.

Original languageEnglish
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
Number of pages12
Publication yearNov 2020
Article number9317953
ISBN (Electronic)9781728196213
Publication statusPublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: 16 Nov 202019 Nov 2020


Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
LandUnited States
ByVirtual, Durham
SponsorIEEE Computer Society Technical Committee on Mathematical Foundations of Computing
SeriesProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

Bibliographical note

Publisher Copyright:
© 2020 IEEE.

Copyright 2021 Elsevier B.V., All rights reserved.

    Research areas

  • Computational Geometry, Data Structures and Algorithms, Fractional Cascading

See relations at Aarhus University Citationformats

ID: 217342166