6 papers · 1 filter
On Range Summary Queries
Peyman Afshani, Pingan Cheng, Aniket Basu Roy +1
We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter and a set of points in $\mat…
Lower Bounds for Intersection Reporting among Flat Objects
Peyman Afshani, Pingan Cheng
Recently, Ezra and Sharir [ES22a] showed an space and query time data structure for ray shooting among triangles in . This improves the…
An Optimal Lower Bound for Simplex Range Reporting
Peyman Afshani, Pingan Cheng
We give a simplified and improved lower bound for the simplex range reporting problem. We show that given a set of points in , any data structure that uses $S…
On Semialgebraic Range Reporting
Peyman Afshani, Pingan Cheng
In the problem of semialgebraic range searching, we are to preprocess a set of points in such that the subset of points inside a semialgebraic region described by $O…
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
Peyman Afshani, Pingan Cheng
In the semialgebraic range searching problem, we are to preprocess points in s.t. for any query range from a family of constant complexity semialgebraic sets, al…
2D Fractional Cascading on Axis-aligned Planar Subdivisions
Peyman Afshani, Pingan Cheng
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,…