Search Results

Documents authored by Cheng, Pingan

Document
DOI: 10.4230/LIPIcs.SoCG.2024.33
Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane

Authors: Timothy M. Chan, Pingan Cheng, and Da Wei Zheng

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1) Semialgebraic range stabbing. We present a data structure for n semialgebraic ranges in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can count the number of ranges containing a query point in O(n^{1/4+ε}) time, for an arbitrarily small constant ε > 0. (The query time bound is likely close to tight for this space bound.) 2) Ray shooting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in O(n^{1/4+ε}) time. (The query bound is again likely close to tight for this space bound, and they improve a result by Ezra and Sharir with near n^{3/2} space and near √n query time.) 3) Intersection counting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in O(n^{1/2+ε}) time. In particular, this implies an O(n^{3/2+ε})-time algorithm for counting intersections between two sets of n algebraic arcs in 2D. (This generalizes a classical O(n^{3/2+ε})-time algorithm for circular arcs by Agarwal and Sharir from SoCG 1991.)
Cite as

Timothy M. Chan, Pingan Cheng, and Da Wei Zheng. Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2024.33,
  author =	{Chan, Timothy M. and Cheng, Pingan and Zheng, Da Wei},
  title =	{{Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.33},
  URN =		{urn:nbn:de:0030-drops-199785},
  doi =		{10.4230/LIPIcs.SoCG.2024.33},
  annote =	{Keywords: Computational geometry, range searching, intersection searching, semialgebraic sets, data structures, polynomial partitioning}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.7
On Range Summary Queries

Authors: Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
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 P of n points in ℝ^d where each point is assigned a color from a set C, and the goal is to build a structure such that given any geometric range γ, we can efficiently find a list of approximate heavy hitters in γ∩P, i.e., colors that appear at least ε |γ∩P| times in γ∩P, as well as their frequencies with an additive error of ε |γ∩P|. In the latter problem, each point is assigned a weight from a totally ordered universe and the query must output a sequence S of 1+1/ε weights such that the i-th weight in S has approximate rank iε|γ∩P|, meaning, rank iε|γ∩P| up to an additive error of ε|γ∩P|. Previously, optimal results were only known in 1D [Wei and Yi, 2011] but a few sub-optimal methods were available in higher dimensions [Peyman Afshani and Zhewei Wei, 2017; Pankaj K. Agarwal et al., 2012]. We study the problems for two important classes of geometric ranges: 3D halfspace and 3D dominance queries. It is known that many other important queries can be reduced to these two, e.g., 1D interval stabbing or interval containment, 2D three-sided queries, 2D circular as well as 2D k-nearest neighbors queries. We consider the real RAM model of computation where integer registers of size w bits, w = Θ(log n), are also available. For dominance queries, we show optimal solutions for both heavy hitter and quantile problems: using linear space, we can answer both queries in time O(log n + 1/ε). Note that as the output size is 1/ε, after investing the initial O(log n) searching time, our structure takes on average O(1) time to find a heavy hitter or a quantile! For more general halfspace heavy hitter queries, the same optimal query time can be achieved by increasing the space by an extra log_w(1/ε) (resp. log log_w(1/ε)) factor in 3D (resp. 2D). By spending extra log^O(1)(1/ε) factors in both time and space, we can also support quantile queries. We remark that it is hopeless to achieve a similar query bound for dimensions 4 or higher unless significant advances are made in the data structure side of theory of geometric approximations.
Cite as

Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei. On Range Summary Queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ICALP.2023.7,
  author =	{Afshani, Peyman and Cheng, Pingan and Basu Roy, Aniket and Wei, Zhewei},
  title =	{{On Range Summary Queries}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.7},
  URN =		{urn:nbn:de:0030-drops-180590},
  doi =		{10.4230/LIPIcs.ICALP.2023.7},
  annote =	{Keywords: Computational Geometry, Range Searching, Random Sampling, Geometric Approximation, Data Structures and Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.3
Lower Bounds for Intersection Reporting Among Flat Objects

Authors: Peyman Afshani and Pingan Cheng

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Recently, Ezra and Sharir [Esther Ezra and Micha Sharir, 2022] showed an O(n^{3/2+σ}) space and O(n^{1/2+σ}) query time data structure for ray shooting among triangles in ℝ³. This improves the upper bound given by the classical S(n)Q(n)⁴ = O(n^{4+σ}) space-time tradeoff for the first time in almost 25 years and in fact lies on the tradeoff curve of S(n)Q(n)³ = O(n^{3+σ}). However, it seems difficult to apply their techniques beyond this specific space and time combination. This pheonomenon appears persistently in almost all recent advances of flat object intersection searching, e.g., line-tetrahedron intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], triangle-triangle intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], or even among flat semialgebraic objects [Agarwal et al., 2022]. We give a timely explanation to this phenomenon from a lower bound perspective. We prove that given a set 𝒮 of (d-1)-dimensional simplicies in ℝ^d, any data structure that can report all intersections with a query line in small (n^o(1)) query time must use Ω(n^{2(d-1)-o(1)}) space. This dashes the hope of any significant improvement to the tradeoff curves for small query time and almost matches the classical upper bound. We also obtain an almost matching space lower bound of Ω(n^{6-o(1)}) for triangle-triangle intersection reporting in ℝ⁴ when the query time is small. Along the way, we further develop the previous lower bound techniques by Afshani and Cheng [Afshani and Cheng, 2021; Afshani and Cheng, 2022].
Cite as

Peyman Afshani and Pingan Cheng. Lower Bounds for Intersection Reporting Among Flat Objects. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2023.3,
  author =	{Afshani, Peyman and Cheng, Pingan},
  title =	{{Lower Bounds for Intersection Reporting Among Flat Objects}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.3},
  URN =		{urn:nbn:de:0030-drops-178536},
  doi =		{10.4230/LIPIcs.SoCG.2023.3},
  annote =	{Keywords: Computational Geometry, Intersection Searching, Data Structure Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.3
On Semialgebraic Range Reporting

Authors: Peyman Afshani and Pingan Cheng

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Semialgebraic range searching, arguably the most general version of range searching, is a fundamental problem in computational geometry. In the problem, we are to preprocess a set of points in ℝ^D such that the subset of points inside a semialgebraic region described by a constant number of polynomial inequalities of degree Δ can be found efficiently. Relatively recently, several major advances were made on this problem. Using algebraic techniques, "near-linear space" data structures [Agarwal et al., 2013; Matoušek and Patáková, 2015] with almost optimal query time of Q(n) = O(n^{1-1/D+o(1)}) were obtained. For "fast query" data structures (i.e., when Q(n) = n^{o(1)}), it was conjectured that a similar improvement is possible, i.e., it is possible to achieve space S(n) = O(n^{D+o(1)}). The conjecture was refuted very recently by Afshani and Cheng [Afshani and Cheng, 2021]. In the plane, i.e., D = 2, they proved that S(n) = Ω(n^{Δ+1 - o(1)}/Q(n)^{(Δ+3)Δ/2}) which shows Ω(n^{Δ+1-o(1)}) space is needed for Q(n) = n^{o(1)}. While this refutes the conjecture, it still leaves a number of unresolved issues: the lower bound only works in 2D and for fast queries, and neither the exponent of n or Q(n) seem to be tight even for D = 2, as the best known upper bounds have S(n) = O(n^{m+o(1)}/Q(n)^{(m-1)D/(D-1)}) where m = binom(D+Δ,D)-1 = Ω(Δ^D) is the maximum number of parameters to define a monic degree-Δ D-variate polynomial, for any constant dimension D and degree Δ. In this paper, we resolve two of the issues: we prove a lower bound in D-dimensions, for constant D, and show that when the query time is n^{o(1)}+O(k), the space usage is Ω(n^{m-o(1)}), which almost matches the Õ(n^{m}) upper bound and essentially closes the problem for the fast-query case, as far as the exponent of n is considered in the pointer machine model. When considering the exponent of Q(n), we show that the analysis in [Afshani and Cheng, 2021] is tight for D = 2, by presenting matching upper bounds for uniform random point sets. This shows either the existing upper bounds can be improved or to obtain better lower bounds a new fundamentally different input set needs to be constructed.
Cite as

Peyman Afshani and Pingan Cheng. On Semialgebraic Range Reporting. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2022.3,
  author =	{Afshani, Peyman and Cheng, Pingan},
  title =	{{On Semialgebraic Range Reporting}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.3},
  URN =		{urn:nbn:de:0030-drops-160117},
  doi =		{10.4230/LIPIcs.SoCG.2022.3},
  annote =	{Keywords: Computational Geometry, Range Searching, Data Structures and Algorithms, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.8
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems

Authors: Peyman Afshani and Pingan Cheng

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
In the semialgebraic range searching problem, we are given a set of n points in ℝ^d and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, then the problem is well-understood: it can be solved using S(n) space and with Q(n) query time with S(n)Q^d(n) = Õ(n^d) where the Õ(⋅) notation hides polylogarithmic factors and this trade-off is tight (up to n^o(1) factors). Consequently, there exists "low space" structures that use O(n) space with O(n^{1-1/d}) query time and "fast query" structures that use O(n^d) space with O(log^{d+1} n) query time. However, for the general semialgebraic ranges, only "low space" solutions are known, but the best solutions match the same trade-off curve as the simplex queries, with O(n) space and Õ(n^{1-1/d}) query time. It has been conjectured that the same could be done for the "fast query" case but this open problem has stayed unresolved. Here, we disprove this conjecture. We give the first nontrivial lower bounds for semilagebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting problem, with Q(n) query time must use S(n) = Ω^o(n³/Q(n)⁵) space where the Ω^o(⋅) notation hides n^o(1) factors, meaning, for Q(n) = O(log^{O(1)}n), Ω^o(n³) space must be used. In addition, we study the problem of reporting the subset of input points between two polynomials of the form Y = ∑_{i=0}^Δ a_i Xⁱ where values a_0,⋯,a_Δ are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of Ω^o(n^{Δ+1}/Q(n)^{Δ²+Δ}), which shows for Q(n) = O(log^{O(1)}n), we must use Ω^o(n^{Δ+1}) space. We also consider the dual problems of semialgebraic range searching, semialgebraic stabbing problems, and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use Ω(n^{2/3}) query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general semialgebraic slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.
Cite as

Peyman Afshani and Pingan Cheng. Lower Bounds for Semialgebraic Range Searching and Stabbing Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2021.8,
  author =	{Afshani, Peyman and Cheng, Pingan},
  title =	{{Lower Bounds for Semialgebraic Range Searching and Stabbing Problems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.8},
  URN =		{urn:nbn:de:0030-drops-138072},
  doi =		{10.4230/LIPIcs.SoCG.2021.8},
  annote =	{Keywords: Computational Geometry, Data Structures and Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact