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

Standard

2D generalization of fractional cascading on axis-aligned planar subdivisions. / Afshani, Peyman; Cheng, Pingan.

Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE, 2020. p. 716-727 9317953 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Vol. 2020-November).

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

Harvard

Afshani, P & Cheng, P 2020, 2D generalization of fractional cascading on axis-aligned planar subdivisions. in Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020., 9317953, IEEE, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2020-November, pp. 716-727, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Virtual, Durham, United States, 16/11/2020. https://doi.org/10.1109/FOCS46700.2020.00072

APA

Afshani, P., & Cheng, P. (2020). 2D generalization of fractional cascading on axis-aligned planar subdivisions. In Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020 (pp. 716-727). [9317953] IEEE. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS Vol. 2020-November https://doi.org/10.1109/FOCS46700.2020.00072

CBE

Afshani P, Cheng P. 2020. 2D generalization of fractional cascading on axis-aligned planar subdivisions. In Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE. pp. 716-727. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Vol. 2020-November). https://doi.org/10.1109/FOCS46700.2020.00072

MLA

Afshani, Peyman and Pingan Cheng "2D generalization of fractional cascading on axis-aligned planar subdivisions". Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Vol. 2020-November). 2020, 716-727. https://doi.org/10.1109/FOCS46700.2020.00072

Vancouver

Afshani P, Cheng P. 2D generalization of fractional cascading on axis-aligned planar subdivisions. In Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE. 2020. p. 716-727. 9317953. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Vol. 2020-November). https://doi.org/10.1109/FOCS46700.2020.00072

Author

Afshani, Peyman ; Cheng, Pingan. / 2D generalization of fractional cascading on axis-aligned planar subdivisions. Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE, 2020. pp. 716-727 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Vol. 2020-November).

Bibtex

@inproceedings{7ba9f2ba5cd043fca622065f21007e8d,
title = "2D generalization of fractional cascading on axis-aligned planar subdivisions",
abstract = "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.",
keywords = "Computational Geometry, Data Structures and Algorithms, Fractional Cascading",
author = "Peyman Afshani and Pingan Cheng",
note = "Publisher Copyright: {\textcopyright} 2020 IEEE. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 ; Conference date: 16-11-2020 Through 19-11-2020",
year = "2020",
month = nov,
doi = "10.1109/FOCS46700.2020.00072",
language = "English",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
pages = "716--727",
booktitle = "Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020",
publisher = "IEEE",

}

RIS

TY - GEN

T1 - 2D generalization of fractional cascading on axis-aligned planar subdivisions

AU - Afshani, Peyman

AU - Cheng, Pingan

N1 - Publisher Copyright: © 2020 IEEE. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2020/11

Y1 - 2020/11

N2 - 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.

AB - 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.

KW - Computational Geometry

KW - Data Structures and Algorithms

KW - Fractional Cascading

UR - http://www.scopus.com/inward/record.url?scp=85100339972&partnerID=8YFLogxK

U2 - 10.1109/FOCS46700.2020.00072

DO - 10.1109/FOCS46700.2020.00072

M3 - Article in proceedings

AN - SCOPUS:85100339972

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 716

EP - 727

BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020

PB - IEEE

T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020

Y2 - 16 November 2020 through 19 November 2020

ER -