Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-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.

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 language | English |
---|---|

Title of host publication | 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 |

Number of pages | 22 |

Publisher | IEEE Computer Society |

Publication year | 2021 |

Publication status | Published - 2021 |

Event | 61st Annual IEEE Symposium on Foundations of Computer Science - Durham, United States Duration: 16 Nov 2020 → 19 Nov 2020 https://focs2020.cs.duke.edu/ |

Conference | 61st Annual IEEE Symposium on Foundations of Computer Science |
---|---|

Land | United States |

By | Durham |

Periode | 16/11/2020 → 19/11/2020 |

Internetadresse |

See relations at Aarhus University Citationformats

ID: 207955723