I've been reading up on data structures for 2D range searching. I've noticed that, in many of the papers I've read, there's close attention paid to the query cost and the space usage required, but often there isn't much discussion about the time required to build the data structure. For example, the paper Orthogonal Range Searching on the RAM, Revisited by Chan et al mentions these space/query time bounds:
Textbook description of range trees implies a solution with $O(n \log n)$ space and $O(\log n + k)$ query time, where $k$ denotes the output size of the query (i.e., the number of points reported). Surprisingly, the best space–query bound for this basic problem is still open. Chazelle gave an $O(n)$-space data structure with $O(\log n + k \log^\epsilon n)$ query time, which has been reduced slightly by Nekrich to $O(\frac{\log n}{\log \log n} + k \log^\epsilon n)$. (Throughout the paper, $\epsilon > 0$ denotes an arbitrarily small constant.) Overmars gave a method with $O(n \log n)$ space and $O(\log \log n + k)$ query time. This query time is optimal for $O(n \log^{O(1)} n)$-space structures in the cell probe model (even for range emptiness in the rank-space case), by reduction from colored predecessor search. Alstrup, Brodal and Rauhe presented two solutions, one achieving $O(n \log^\epsilon n)$ space and optimal $O(\log \log n + k)$ query time, and one with $O(n \log \log n)$ space and $O(\log^2 \log n + k \log \log n)$ query time, both improving Chazelle’s earlier data structures with the corresponding space bounds.
Here's another example from the recent paper New Data Structures for Orthogonal Range Reporting and Range Minima Queries by Nekrich:
According to the lower bound of Pătrașcu, any data structure that consumes $O(n \cdot polylog(n))$ space requires $\Omega(\frac{\log n}{\log \log n})$ time to answer four-dimensional queries; this lower bound is also valid for emptiness queries.
I did notice, however, that in Chazelle's A Functional Approach to Data Structures and its use in Multidimensional Searching he mentioned that the data structures he proposes all take time $O(n \log n)$ to construct.
Based on what I'm reading, I'm assuming that one of the following is true:
- The papers I'm reading are mostly in a vein of research that specifically is looking at cell-probe lower bounds for space usage with the goal of seeing whether it's possible to build any data structure at all, regardless of construction efficiency, that meets the given query times.
- I'm skimming these papers too quickly and if I were to read more closely I would see that, indeed, the construction times are listed there plain as day.
- I'm totally new to this field and am missing something obvious. :-)
- There hasn't been much interest in data structure construction time, so people haven't been focusing too much on it.
My guess is that it's a mix of (1), (2), and (3) and that (4) is probably false. However, I figured it would be good to ask in case anyone had any advice or guidance to offer.
