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

We present the first optimal randomized algorithm for constructing the order-k Voronoi diagram of n points in two dimensions. The expected running time is O(n log n + nk), which improves the previous, two-decades- old result of Ramos (SoCG’99) by a 2O(log* k) factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA’22) in combination with Ramos's cutting construction, to reduce the problem to verifying an order-k Voronoi diagram, and (ii) solve the verification problem by a new divide-and-conquer algorithm using planar-graph separators.

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

We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter $\varepsilon$ and a set $P$ of $n$ points in $\mathbb{R}^d$ where each point is assigned a color from a set $C$, and we want to build a structure s.t. given any geometric range $γ$, we can efficiently find a list of approximate heavy hitters in $γ\cap P$, i.e., colors that appear at least $\varepsilon |γ\cap P|$ times in $γ\cap P$, as well as their frequencies with an additive error of $\varepsilon |γ\cap 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/\varepsilon$ weights s.t. the $i$-th weight in $S$ has approximate rank $i\varepsilon|γ\cap P|$, meaning, rank $i\varepsilon|γ\cap P|$ up to an additive error of $\varepsilon|γ\cap P|$. Previously, optimal results were only known in 1D [WY11] but a few sub-optimal methods were available in higher dimensions [AW17, ACH+12]. We study the problems for 3D halfspace and dominance queries. We consider the real RAM model with integer registers of size $w=Θ(\log n)$ bits. 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/\varepsilon)$. Note that as the output size is $\frac{1}{\varepsilon}$, 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\frac{1}{\varepsilon}$ (resp. $\log\log_w\frac{1}{\varepsilon}$) factor in 3D (resp. 2D). By spending extra $\log^{O(1)}\frac{1}{\varepsilon}$ factors in time and space, we can also support quantile queries.

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, the problem is well-understood: It can be solved using S(n) space and with Q(n) query time with \(S(n)Q(n)^d = \tilde{O}(n^d),\) where the \(\tilde{O}(\cdot)\) notation hides polylogarithmic factors and this trade-off is tight (up to n o (1) factors). In particular, there exist “low space” structures that use O(n) space with O ( n 1-1/ d } ) query time [ 8 , 25 ] and “fast query” structures that use O ( n d ) space with O (log n ) query time [ 9 ]. However, for general semialgebraic ranges, only “low space” solutions are known, but the best solutions [ 7 ] match the same trade-off curve as simplex queries, with O ( n ) space and \(\tilde{O}(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 semialgebraic 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, with Q ( n ) query time must use \(S(n)=\overset{\scriptscriptstyle o}{\Omega }(n^3/Q(n)^5)\) space, where the \(\overset{\scriptscriptstyle o}{\Omega }(\cdot)\) notation hides \(n^{o(1)}\) factors, meaning, for \(Q(n)=\log ^{O(1)}n\) , \(\overset{\scriptscriptstyle o}{\Omega }(n^3)\) space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by \(\lbrace (x,y)\in \mathbb {R}^2:P(x)\le y\le P(x)+w\rbrace\) , where \(P(x)=\sum _{i=0}^\Delta a_i x^i\) is a univariate polynomial of degree Δ and \(a_0, \ldots , a_\Delta , w\) are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of \(\overset{\scriptscriptstyle o}{\Omega }(n^{\Delta +1}/Q(n)^{(\Delta +3)\Delta /2})\) , which implies that for \(Q(n)=\log ^{O(1)}n\) , we must use \(\overset{\scriptscriptstyle o}{\Omega }(n^{\Delta +1})\) space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching 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 \(\Omega (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 polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.

In the problem of semialgebraic range searching, we are to preprocess a set of points in $\mathbb{R}^D$ such that the subset of points inside a semialgebraic region described by $O(1)$ polynomial inequalities of degree $Δ$ can be found efficiently. Relatively recently, several major advances were made on this problem. Using algebraic techniques, "near-linear space" structures [AMS13,MP15] with almost optimal query time of $Q(n)=O(n^{1-1/D+o(1)})$ were obtained. For "fast query" structures (i.e., when $Q(n)=n^{o(1)}$), it was conjectured that a structure with space $S(n) = O(n^{D+o(1)})$ is possible. The conjecture was refuted recently by Afshani and Cheng [AC21]. In the plane, 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 current upper bound is $S(n) = O(n^{\boldsymbol{m}+o(1)}/Q(n)^{(\boldsymbol{m}-1)D/(D-1)})$ where $\boldsymbol{m}=\binom{D+Δ}{D}-1 = Ω(Δ^D)$ is the maximum number of parameters to define a monic degree-$Δ$ $D$-variate polynomial, for any $D,Δ=O(1)$. In this paper, we resolve two of the issues: we prove a lower bound in $D$-dimensions and show that when $Q(n)=n^{o(1)}+O(k)$, $S(n)=Ω(n^{\boldsymbol{m}-o(1)})$, which is almost tight 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 [AC21] 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 a new fundamentally different input set is needed to get a better lower bound.

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.

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 π of G, we can find the predecessor of q in all the sets associated with the vertices of π. 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+|π|) 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 π 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 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 π is a path, then queries can be answered in O(log n+|π|+ min{|π|√{log n},α(n)√{|π|}log n}) 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}) and this bound is once again tight in both cases.