We prove that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity, where the optimality is defined with respect to both the input and output sizes. This explains why the best previous algorithms achieved an optimal I/O bound at the cost of sub-optimal running time (Goodrich et al. [FOCS, 1993]). To the best of our knowledge, the impossibility of simultaneous optimality was only shown previously for the permutation problem by Brodal and Fagerberg [STOC, 2003]. Our results imply that no optimal deterministic output-sensitive cache-oblivious algorithm exists for either problem. In addition, we present simple deterministic algorithms that match our lower bounds and that provide a trade-off between time and I/Os. On the other hand, a simple modification of our deterministic algorithm results in a randomized algorithm that simultaneously achieves optimal (worst-case) time and optimal expected I/O bounds.

We study the problem of proving lower bounds in the Priority CRCW PRAM for the query time of several fundamental and well-studied data structures, motivated by the observation that, for many basic data structure problems, no proven limits on parallelism exist. We use the cell-probe model, which has been studied extensively in the sequential setting and where for all the problems under consideration, Ω(log n/log log n) query time lowers bound exist. However, we report that in the parallel settings, some of these problems become "easy", i.e., admit solutions with constant query time in the Common CRCW PRAM using polylogarithmic number of processors, while others become "hard", via the following result. We prove query time lower bounds (in the Priority CRCW PRAM model) via a careful combination of some of the cell-probe lower bound techniques with ideas from the PRAM area. While the actual statement of the lower bounds are complicated, they all can be simplified to an Ω(log log n) query time lower bound under the most reasonable settings, and with polylogarithmic processors. The fact that all these problems admit an Ω(log n/log log n) query lower bound in the sequential settings implies that most of the cell-probe lower bound techniques cannot be generalized to the CRCW PRAM model of computation, meaning, the landscape of data structure lower bounds in the CRCW PRAM models of computation is more complicated.

Inspired by the classical fractional cascading technique, we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph $\mathbf{G}$ with bounded degree together with a set $H_v$ of 3D hyperplanes associated with every vertex of $v$ of $\mathbf{G}$. The goal is to store the input such that given a query point $q\in \mathbb{R}^3$ and a connected subgraph $\mathbf{H}\subset \mathbf{G}$, we can decide if $q$ is below or above the lower envelope of $H_v$ for every $v\in \mathbf{H}$. We show that using linear space, it is possible to answer queries in roughly $O(\log n + |\mathbf{H}|\sqrt{\log n})$ time which improves trivial bound of $O(|\mathbf{H}|\log n)$ obtained by using planar point location data structures. Our data structure can in fact answer more general queries (it combines with shallow cuttings) and it even works when $\mathbf{H}$ is given one vertex at a time. We show that this has a number of new applications and in particular, we give improved solutions to a set of natural data structure problems that up to our knowledge had not seen any improvements. We believe this is a very surprising result because obtaining similar results for the planar point location problem was known to be impossible.

We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius δ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most δ) or they are "ε-far" (for 0 < ε < 2) from being similar, i.e., more than an ε-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are t-approximate shortest paths in the ambient metric space, for some t ≪ n. The first algorithm uses O(t/ε log t/ε) queries and is given the value of t in advance. The second algorithm does not have explicit knowledge of the value of t and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly O({t³+t² log n}/ε) queries ignoring logarithmic factors in t. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of t-straight curves, our algorithms can be used for (1+ε')-approximate testing using essentially the same bounds as stated above with an additional factor of poly(1/(ε')).

In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.

We study the predecessor search problem in the classical PRAM model of computation. In this problem, the input is a set of n ℓ-bit integers and the goal is to store the input in a data structure of size S (n ) such that given a query value q, the predecessor of q can be found efficiently. This is a very classical problem with an extensive history.

We investigate coresets for approximating the cost with respect to median queries. In this problem, we are given a set of points $P\subset \mathbb{R}^d$ and median queries are $\sum_{p\in P} ||p-c||$ for any point $c\in \mathbb{R}^d$. Our goal is to compute a small weighted summary $S\subset P$ such that the cost of any median query is approximated within a multiplicative $(1\pm\varepsilon)$ factor. We provide matching upper and lower bounds on the number of points contained in $S$ of the order $\tilde{\Theta}\left(\varepsilon^{-d/(d+1)}\right)$.

In colored range counting (CRC), the input is a set of points where each point is assigned a “color” (or a “category”) and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data. However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through a reduction from the orthogonal vectors problem.

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.

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$. When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$. Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

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 colored range counting (CRC), the input is a set of points where each point is assigned a "color" (or a "category") and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data. However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through reductions from the orthogonal vectors problem.

The rise of online map services drives data owners to outsource spatial data to potentially untrusted database providers. Query results are provided along with verification objects that allow confirming their authenticity. Such authentication schemes have been proposed for several spatial and geometric queries, as well as for median queries in one dimension. However, to date, no authentication mechanism exists for centerpoint queries, which return a point lying in the middle of other points in multidimensional space. In this paper, we propose an authentication scheme for centerpoint queries, grounded on the algorithm for centerpoint queries on a finite planar set of points and authenticated aggregation R-trees and accompanying authenticated aggregation queries. We also provide methods for finding the centerpoint of a subset of the complete data set, and implement a range-based method. Our solution has a worst-case time-complexity of O(n log n) and space-complexity of O(n). Our experimental study confirms these claims.

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.

We investigate the limits of one of the fundamental ideas in data structures: fractional cascading. This is an important data structure technique to speed up repeated searches for the same key in multiple lists and it has numerous applications. Specifically, the input is a “catalog” graph, Gcat, of constant degree together with a list of values assigned to every vertex of Gcat. The goal is to preprocess the input such that given a connected subgraph G′ of Gcat and a single query value q, one can find the predecessor of q in every list that belongs to G′. The classical result by Chazelle and Guibas shows that in a pointer machine, this can be done in the optimal time of where n is the total number of values. However, if insertion and deletion of values are allowed, then the query time slows down to . If only insertions (or deletions) are allowed, then once again, an optimal query time can be obtained but by using amortization at update time. We prove a lower bound of on the worst-case query time of dynamic fractional cascading, when queries are paths of length O(log n). The lower bound applies both to fully dynamic data structures with amortized polylogarithmic update time and incremental data structures with polylogarithmic worst-case update time. As a side, this also proves that amortization is crucial for obtaining an optimal incremental data structure. This is the first non-trivial pointer machine lower bound for a dynamic data structure that breaks the Ω(log n) barrier. In order to obtain this result, we develop a number of new ideas and techniques that hopefully can be useful to obtain additional dynamic lower bounds in the pointer machine model.

Database cracking (DBC) provides an adaptive data storage environment that meets the needs of modern applications in business and science, reorganizing data on demand and adapting indexes on the fly, automatically, and collaterally to query processing. Despite intensive research on cracking and other adaptive indexing variants, their theoretical side has scarcely been investigated. Yet, quite surprisingly, as we show, an antecedent of database cracking in a pure, no-frills form had been developed in the theory community 24 years ahead of its time by the name of deferred data structuring (DDS). While lacking system implementations, DDS corresponds to what we would call, by the terminology used in the database community, materialization-based data-driven center cracking for point lookup queries, as well as a stochastic variant thereof. Further, DDS has gone beyond regular cracking proposals by suggesting a policy that reorganizes index ranges along the median of a sample set, i.e., a mediocre element. In this paper, we reanalyze state-of-the-art database cracking algorithms with the benefit of hindsight provided by deferred data structuring, and propose new alternatives that use a mediocre element as cracking pivot instead of a random or a median one. In a thorough experimental study, we determine that a logarithmic or linear sample size yields best performance on a standard benchmark across the board of cracking algorithms.

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.

In this paper we study lower bounds for a variant of jumbled-indexing problem: given an input string S on an alphabet Σ = {σ1,…, σλ}, store it in a data structure such that given frequencies f1,…, fλ, one can find all the substrings S’ of S where the frequency of the character σi is fi, for 1 ≤ i ≤ λ. This is a very interesting and challenging text indexing problem and it has received significant attention lately, both in the string-indexing community as well as in the theory community. It is known that when λ = 2, one can use a linear-size data structure to decide whether there exists a substring that matches the query in constant time [10]. It is also known [1] that for constant λ ≥ 3, then there exists a constant αλ such that it is not possible to achieve both O(n2−αλ) preprocessing time and O(n1−aλ) query time. We study a variant of the problem where the goal is to report all the substrings of S that match a given jumbled-indexing query. Assuming the data structure operates in the pointer machine model, we prove unconditional space lower bounds that also apply to binary alphabets: we show that if the data structure has the query time of O(n0.5−o(1) + k), where k is the output size of the query, then it must consume Ω(n2−o(1)) space. The o(1) term in our lower bound is at most where log(·) notation denotes the iterative log function (i.e., log(10) n = log log log log log log log log log log n). This result has a number of interesting consequences. First, it shows that reporting all the matches is significantly harder than deciding whether a match exists, at least for the binary alphabet. This was surprising for us since we believed that in order for jumbled-indexing to be difficult, the alphabet size must be at least 3. Second, from a technical point of view, we make connections between this problem and the area of additive combinatorics as well as random walks. Previously, Chan and Lewenstein [6] had shown the connections between this problem and the area of additive combinatorics from an upper bound point of view, however, we use fundamental theorems from additive combinatorics but these tools are quite different from the theorems used in [6]. In our opinion, the fact that additive combinatorics appears in our lower bound approach as well as in the upper bound approach of Chan and Lewenstein [6] is noteworthy and demands further investigation. We believe our results open up a few new venues for research. For example, we believe it is interesting to study whether it is possible to build a data structure that uses O(n) space s.t., it can report all the matches to a jumble-indexing query in O(n2/3 + k) time; this is even interesting for a binary alphabet.

We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle’s result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao’s influential result had shown that the problem is already non-trivial in one dimension [Yao, 1982]: using m units of space, the query time Q(n) must be Omega(alpha(m,n) + n/(m-n+1)) where alpha(*,*) is the inverse Ackermann’s function, a very slowly growing function. In d dimensions, Bernard Chazelle [Chazelle, 1990] proved that the query time must be Q(n) = Omega((log_beta n)^{d-1}) where beta = 2m/n. Chazelle’s lower bound is known to be tight for when space consumption is "high" i.e., m = Omega(n log^{d+epsilon}n). We have two main results. The first is a lower bound that shows Chazelle’s lower bound was not tight for "low space": we prove that we must have m Q(n) = Omega(n (log n log log n)^{d-1}). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.

We revisit the range sampling problem: the input is a set of points where each point is associated with a real-valued weight. The goal is to store them in a structure such that given a query range and an integer $k$, we can extract $k$ independent random samples from the points inside the query range, where the probability of sampling a point is proportional to its weight. This line of work was initiated in 2014 by Hu, Qiao, and Tao and it was later followed up by Afshani and Wei. The first line of work mostly studied unweighted but dynamic version of the problem in one dimension whereas the second result considered the static weighted problem in one dimension as well as the unweighted problem in 3D for halfspace queries. We offer three main results and some interesting insights that were missed by the previous work: We show that it is possible to build efficient data structures for range sampling queries if we allow the query time to hold in expectation (the first result), or obtain efficient worst-case query bounds by allowing the sampling probability to be approximately proportional to the weight (the second result). The third result is a conditional lower bound that shows essentially one of the previous two concessions is needed. For instance, for the 3D range sampling queries, the first two results give efficient data structures with near-linear space and polylogarithmic query time whereas the lower bound shows with near-linear space the worst-case query time must be close to $n^{2/3}$, ignoring polylogarithmic factors. Up to our knowledge, this is the first such major gap between the expected and worst-case query time of a range searching problem.

We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible.

Modern tracking technology has made the collection of large numbers of densely sampled trajectories of moving objects widely available. We consider a fundamental problem encountered when analysing such data: Given n polygonal curves S in ℝd, preprocess S into a data structure that answers queries with a query curve q and radius ρ for the curves of S that have Fréchet distance at most ρ to q. We initiate a comprehensive analysis of the space/query-time tradeoff for this data structuring problem. Our lower bounds imply that any data structure in the pointer model model that achieves Q(n) + O(k) query time, where k is the output size, has to use roughly n((n/Q(n))2) space in the worst case, even if queries are mere points (for the discrete Fréchet distance) or line segments (for the continuous Fréchet distance). More importantly, we show that more complex queries and input curves lead to additional logarithmic factors in the lower bound. Roughly speaking, the number of logarithmic factors added is linear in the number of edges added to the query and input curve complexity. This means that the space/query time tradeoff worsens by an exponential factor of input and query complexity. This behaviour addresses an open question (see [1, 9]) in the range searching literature concerning multilevel partition trees which may be of independent interest, namely, whether it is possible to avoid the additional logarithmic factors in the space and query time of a multilevel partition tree. We answer this question negatively. On the positive side, we show we can build data structures for the Fréchet distance by using semialgebraic range searching. The space/query-time tradeoff of our data structure for the discrete Fréchet distance is in line with the lower bound, as the number of levels in the data structure is O(t), where t denotes the maximal number of vertices of a curve. For the continuous Fréchet distance, the number of levels increases to O(t2).

Let T be a terrain, and let P be a set of points (locations) on its surface. An important problem in Geographic Information Science (GIS) is computing the visibility index of a point p on P, that is, the number of points in P that are visible from p. The total visibility-index problem asks for computing the visibility index of every point in P. Most applications of this problem involve 2-dimensional terrains represented by a grid of n × n square cells, where each cell is associated with an elevation value, and P consists of the center-points of these cells. Current approaches for computing the total visibility-index on such a terrain take at least quadratic time with respect to the number of the terrain cells. While finding a subquadratic solution to this 2D total visibility-index problem is an open problem, surprisingly, no subquadratic solution has been proposed for the one-dimensional (1D) version of the problem; in the 1D problem, the terrain is an x-monotone polyline, and P is the set of the polyline vertices. We present an O(n log2 n) algorithm that solves the 1D total visibility-index problem in the RAM model. Our algorithm is based on a geometric dualization technique, which reduces the problem into a set of instances of the red-blue line segment intersection counting problem. We also present a parallel version of this algorithm, which requires O(log2 n) time and O(n log2 n) work in the CREW PRAM model. We implement a naive O(n2) approach and three variations of our algorithm: one employing an existing red-blue line segment intersection algorithm and two new approaches that perform the intersection counting by leveraging features specific to our problem. We present experimental results for both serial and parallel implementations on large synthetic and real-world datasets, using two distinct hardware platforms. Results show that all variants of our algorithm outperform the naive approach by several orders of magnitude on large datasets. Furthermore, we show that our new intersection counting implementations achieve more than 8 times speedup over the existing red-blue line segment intersection algorithm. Our parallel implementation is able to process a terrain of 224 vertices in under 1 minute using 16 cores, achieving more than 7 times speedup over serial execution.

We study permuting and batched orthogonal geometric reporting problems in the External Memory Model (EM), assuming indivisibility of the input records. Our main results are twofold. First, we prove a general simulation result that essentially shows that any permutation algorithm (resp. duplicate removal algorithm) that does alpha*N/B I/Os (resp. to remove a fraction of the existing duplicates) can be simulated with an algorithm that does alpha phases where each phase reads and writes each element once, but using a factor alpha smaller block size. Second, we prove two lower bounds for batched rectangle stabbing and batched orthogonal range reporting queries. Assuming a short cache, we prove very high lower bounds that currently are not possible with the existing techniques under the tall cache assumption.

In the independent range sampling (IRS) problem, given an input set P of n points in R^d, the task is to build a data structure, such that given a range R and an integer t >= 1, it returns t points that are uniformly and independently drawn from P cap R. The samples must satisfy inter-query independence, that is, the samples returned by every query must be independent of the samples returned by all the previous queries. This problem was first tackled by Hu, Qiao and Tao in 2014, who proposed optimal structures for one-dimensional dynamic IRS problem in internal memory and one-dimensional static IRS problem in external memory. In this paper, we study two natural extensions of the independent range sampling problem. In the first extension, we consider the static IRS problem in two and three dimensions in internal memory. We obtain data structures with optimal space-query tradeoffs for 3D halfspace, 3D dominance, and 2D three-sided queries. The second extension considers weighted IRS problem. Each point is associated with a real-valued weight, and given a query range R, a sample is drawn independently such that each point in P cap R is selected with probability proportional to its weight. Walker's alias method is a classic solution to this problem when no query range is specified. We obtain optimal data structure for one dimensional weighted range sampling problem, thereby extending the alias method to allow range queries.

Dictionaries remain the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extract-min. In a RAM, all such operations take O(log n) time on n elements. Dictionaries are often cross-referenced as follows. Consider a set of tuples {〈ai,bi,ci…〉}. A database might include more than one dictionary on such a set, for example, one indexed on the a ‘s, another on the b‘s, and so on. Once again, in a RAM, inserting into a set of L cross-referenced dictionaries takes O(L log n) time, as does deleting. The situation is more interesting in external memory. On a Disk Access Machine (DAM), B-trees achieve O(logB N) I/Os for insertions and deletions on a single dictionary and K-element range queries take optimal O(logB N + K/B) I/Os. These bounds are also achievable by a B-tree on cross-referenced dictionaries, with a slowdown of an L factor on insertion and deletions. In recent years, both the theory and practice of external- memory dictionaries has been revolutionized by write- optimization techniques. A dictionary is write optimized if it is close to a B-tree for query time while beating B-trees on insertions. The best (and optimal) dictionaries achieve a substantially improved insertion and deletion cost of amortized I/Os on a single dictionary while maintaining optimal O(log1+B∊ N + K/B)- I/O range queries. Although write optimization still helps for insertions into cross-referenced dictionaries, its value for deletions would seem to be greatly reduced. A deletion into a cross- referenced dictionary only specifies a key a. It seems to be necessary to look up the associated values b, c … in order to delete them from the other dictionaries. This takes Ω(logB N) I/Os, well above the per-dictionary write-optimization budget of So the total deletion cost is In short, for deletions, write optimization offers an advantage over B-trees in that L multiplies a lower order term, but when L = 2, write optimization seems to offer no asymptotic advantage over B-trees. That is, no known query- optimal solution for pairs of cross-referenced dictionaries seem to beat B-trees for deletions. In this paper, we show a lower bound establishing that a pair of cross-referenced dictionaries that are optimal for range queries and that supports deletions cannot match the write optimization bound available to insert-only dictionaries. This result thus establishes a limit to the applicability of write-optimization techniques on which many new databases and file systems are based.

We prove the existence of an algorithm A for computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A ′ in a certain class A , the running time of A on input σ is at most a constant factor times the running time of A ′ on the worst possible permutation of σ for A ′. In fact, we can establish a stronger property: for every sequence σ of points and every algorithm A ′, the running time of A on σ is at most a constant factor times the average running time of A ′ over all permutations of σ. We call algorithms satisfying these properties instance optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input are given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] or Chan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic L ∞ -close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on online orthogonal range searching in 2D and online half-space range reporting in 2D and 3D.

In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in d-dimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed. First we give a non-parameterized algorithm for both problems in O*(2^n) (where the O*(.) notation hides polynomial factors of n) time and polynomial space, beating a previous exponential-space result. Combining this with incidence bounds similar to the famous Szemeredi-Trotter bound, we present a Curve Cover algorithm with running time O*((Ck/log k)^((d-1)k)), where C is some constant. Our result improves the previous best times O*((k/1.35)^k) for Line Cover (where d=2), O*(k^(dk)) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in R^3 with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k).

We study data structure problems related to document indexing and pattern matching queries and our main contribution is to show that the pointer machine model of computation can be extremely useful in proving high and unconditional lower bounds that cannot be obtained in any other known model of computation with the current techniques. Often our lower bounds match the known space-query time trade-off curve and in fact for all the problems considered, there is a very good and reasonable match between our lower bounds and the known upper bounds, at least for some choice of input parameters. The problems that we consider are set intersection queries (both the reporting variant and the semi-group counting variant), indexing a set of documents for two-pattern queries, or forbidden-pattern queries, or queries with wild-cards, and indexing an input set of gapped-patterns (or two-patterns) to find those matching a document given at the query time.

In this paper, we study the problem of computing the maxima of a set of n points in three dimensions with integer coordinates and show that in a word RAM, the maxima can be found in O (nloglogn/h n) deterministic time in which h is the output size. For h = n1–α this is O(n log(1/α)). This improves the previous O(n log log h) time algorithm and can be considered surprising since it gives a linear time algorithm when α > 0 is a constant, which is faster than the current best deterministic and randomized integer sorting algorithms. We observe that improving this running time is most likely difficult since it requires breaking a number of important barriers, even if randomization is allowed. Additionally, we show that the same deterministic running time could be achieved for performing n point location queries in an arrangement of size h. Finally, our maxima result can be extended to higher dimensions by paying a logn/h n factor penalty per dimension. This has further interesting consequences for example it preserves the linear running time when h ≤ n1 – α, for a constant α > 0, and thus it shows that for a variety of input distributions the maxima can be computed in linear expected time without knowing the distribution.

In the concurrent range reporting (CRR) problem, the input is L disjoint sets S1, …, SL of points in ℝd with a total of N points. The goal is to preprocess the sets into a structure such that, given a query range r and an arbitrary set Q ⊆ {1, …, L}, we can efficiently report all the points in Si ∩ r for each i ∊ Q. The problem was studied as early as 1986 by Chazelle and Guibas [9] and has recently re-emerged when studying higher-dimensional complexity of orthogonal range reporting [2, 3]. We focus on the one- and two-dimensional cases of the problem. We prove that in the pointer-machine model (as well as comparison models such as the real RAM model), answering queries requires Ω(|Q| log(L/|Q|) + logN + K) time in the worst case, where K is the number of output points. In one dimension, we achieve this query time with a linear-space dynamic data structure that requires optimal O(log N) time to update. We also achieve this query time in the static case for dominance and halfspace queries in the plane. For three-sided ranges, we get close to within an inverse Ackermann (α(·)) factor: we answer queries in O(|Q| log(L/|Q|)α(L)+logN + K) time, improving the best previously known query times of O(|Q|log(N/|Q|) + K) and O(2LL + log N + K). Finally, we give an optimal data structure for three-sided ranges for the case L = O(logN).

Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that given a set of n three-dimensional points, they construct optimal size (single and multiple) shallow cuttings for orthogonal dominance ranges. In particular, we show how to construct a single shallow cutting in O(n log n) worst case time, using O(n) space. We also show how to construct in the same complexity, a logarithmic number of shallow cuttings of the input simultaneously. Our algorithms are optimal in the comparison and the algebraic comparison models, and they are an important step forward, since only polynomial guarantees were previously achieved for the deterministic construction of shallow cuttings, even in three dimensions. In fact, our methods yield the first worst case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilised to support the queries efficiently.

We investigate one of the fundamental areas in computational geometry: lower bounds for range reporting problems in the pointer machine and the external memory models. We develop new techniques that lead to new and improved lower bounds for simplex range reporting as well as some other geometric problems.

In this paper, we consider two fundamental problems in the pointer machine model of computation, namely orthogonal range reporting and rectangle stabbing. Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space in a data structure, such that the t points in an axis-aligned query rectangle can be reported efficiently. Rectangle stabbing is the "dual" problem where a set of n axis-aligned rectangles should be stored in a data structure, such that the t rectangles that contain a query point can be reported efficiently. Very recently an optimal O(log n+t) query time pointer machine data structure was developed for the three-dimensional version of the orthogonal range reporting problem. However, in four dimensions the best known query bound of O(log2n / log log n + t) has not been improved for decades.

Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each point's uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline.

We study the following problem: Given an array A storing N real numbers, preprocess it to allow fast reporting of the K smallest elements in the subarray A[i, j] in sorted order, for any triple (i, j, K) with 1 ≤ i ≤ j ≤ N and 1 ≤ K ≤ j − i + 1. We are interested in scenarios where the array A is large, necessitating an I/O-efficient solution. For a parameter f with 1 ≤ f ≤ logm n, we construct a data structure that uses O((N/f) logm n) space and achieves a query bound of O(logB N + fK/B) I/Os,1 where B is the block size, M is the size of the main memory, n: = N/B, and m: = M/B. Our main contribution is to show that this solution is nearly optimal. To be precise, we show that achieving a query bound of O(logα n + fK/B) I/Os, for any constant α, requires space, assuming B = Ω(log N). For M ≥ B1+ε, this is within a log logm n factor of the upper bound. The lower bound assumes indivisibility of records and holds even if we assume K is always set to j − 1 + 1. We also show that it is the requirement that the K smallest elements be reported in sorted order which makes the problem hard. If the K smallest elements in the query range can be reported in any order, then we can obtain a linear-size data structure with a query bound of O(logB N + K/B) I/Os.

We provide improved bounds on the size of cache-oblivious range reporting data structures that achieve the optimal query bound of O(logB N + K/B) block transfers. Our first main result is an O(N √log N log log N)-space data structure that achieves this query bound for 3-d dominance reporting and 2-d three-sided range reporting. No cache-oblivious o(N log N/ log log N)-space data structure for these problems was known before, even when allowing a query bound of O(log2O(1)N + K/B) block transfers.1 Our result also implies improved space bounds for general 2-d and 3-d orthogonal range reporting. Our second main result shows that any cache-oblivious 2-d three-sided range reporting data structure with the optimal query bound has to use Ω(N logε N) space, thereby improving on a recent lower bound for the same problem. Using known transformations, the lower bound extends to 3-d dominance reporting and 3-d halfspace range reporting.

Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space, such that the k points in an axis-orthogonal query box can be reported efficiently. While the 2-d version of the problem was completely characterized in the pointer machine model more than two decades ago, this is not the case in higher dimensions.

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K/B) block transfers in the worst case, where K is the size of the query output.

We present cache-oblivious solutions to two important variants of range searching: range reporting and approximate range counting. The main contribution of our paper is a general approach for constructing cache-oblivious data structures that provide relative (1+ε)-approximations for a general class of range counting queries. This class includes three-sided range counting, 3-d dominance counting, and 3-d halfspace range counting. Our technique allows us to obtain data structures that use linear space and answer queries in the optimal query bound of O(logB(N/K)) block transfers in the worst case, where K is the number of points in the query range. Using the same technique, we also obtain the first approximate 3-d halfspace range counting and 3-d dominance counting data structures with a worst-case query time of O(log(N/K)) in internal memory.

In orthogonal range reporting we are to preprocess N points in d-dimensional space so that the points inside a d-dimensional axis-aligned query box can be reported efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry. In this paper we provide a number of improvements for three and higher dimensional orthogonal range reporting: In the pointer machine model, we improve all the best previous results, some of which have not seen any improvements in almost two decades. In the I/O-model, we improve the previously known three-dimensional structures and provide the first (non-trivial) structures for four and higher dimensions.

We prove the existence of an algorithm A for computing 2-d or 3-dconvex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A' in a certain class A, the running time of A on the worst permutation of S for A is at most a constant factor times the running time of A' on the worst permutation of S for A'. In fact, we can establish a stronger property: for every S and A', the running time of A on S is at most a constant factor times the average running time of A' over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap(1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, offline orthogonal range searching in 2-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d. The theory we develop also neatly reveals connections to entropy-dependent data structures, and yields as a byproduct new expected case results, e.g., for on-line orthogonal range counting in 2-d.

We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in O(log n + k) time. The data structure can be built in O(n log n) expected time. The previous methods with optimal query time required superlinear (O(n log log n)) space. We also mention consequences, for example, to higher dimensions and to external-memory data structures. As an aside, we partially answer another open question concerning the crossing number in Matoušek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).

We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected sizewhich can answer 3D approximate halfspace range counting queries in O(log n/k) expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo.In addition, we describe new results for several related problems, includingapproximate Tukey depth queries in 3D, approximate regression depthqueries in 2D, and approximate linear programming with violations inlow dimensions.