Conference Papers

2023

Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei, On Range Summary Queries, to appear in ICALP'23

Mini Abstract: We study two extensions to range search queries to better meet the challenge posed by the modern big data era: range approximate heavy hitter queries and range approximate quantile queries. We show that with near linear space, we can build a structure that is able to answer the two extensions efficiently with polylogarithmic query time for halfspace and dominance queries in 3D.

Preprint

Peyman Afshani and Pingan Cheng, Lower Bounds for Intersection Searching among Flat Objects, to appear in SoCG'23

Mini Abstract: In recent years, several new results were discovered for the classical range intersection searching problems using the new polynomial method. However, the new results were limited to specific space-time combinations. We provide an explanation to this phenomenon by presenting a lower bound which shows we cannot improve the old space-time tradeoff too much when the query time is polylogarithmic.

Preprint

Peyman Afshani and Pingan Cheng, An Optimal Lower Bound for Simplex Range Reporting, in SoSA'23

Mini Abstract: Simplex range reporting is a classical problem in computational geometry. In this work, we show a tight lower bound for linear space simplex range reporting data structures. This is the first tight lower bound for the problem, and it significantly simplifies previous lower bound results.

Published Version

2022
Peyman Afshani and Pingan Cheng, On Semialgebraic Range Reporting, in SoCG'22

Mini Abstract: We address two issues of our 2021 paper. We show a lower bound for semialgebraic range reporting for all dimensions and for polynomials with the maximum coefficients. This essentially closes the problem for the fast query case.
Published Version, Full Version

2021
Peyman Afshani and Pingan Cheng, Lower Bounds for Semialgebraic Range Searching and Stabbing Problems, in SoCG'21 (Best Paper)

Mini Abstract: Range searching with semialgebraic sets is arguably the most general version of range searching. The study of the problem dates back to 1980s, but efficient upper bounds were discovered only very recently, one in 2013 and another in 2018, for two special cases. In this work, we show the first nontrivial lower bound for the problem which matches the fast-query version (polylogarithmic query time) upper bound.

Published Version, Full Version 

2020
Peyman Afshani and Pingan Cheng, 2D Generalization of Fractional Cascading on Axis-aligned Planar Subdivisions, in FOCS'20 

Mini Abstract: The famous fractional cascading technique tells us we can solve concurrent point locations (predecessor searching) in 1D in the optimal logarithmic query time and linear space. It has been shown that this technique cannot be generalized to higher dimensions. In this paper, we show that we can  circumvent this restriction for the special case of 2D orthogonal subdivisions by presenting new upper and matching lower bounds to the problem.

Published Version, Full Version