# Tradeoff Bounds for Halfspace Range Counting

What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff. According to Matousek's seminal 1993 paper (Theorem 6.2, Range Searching with Efficient Hierarchical Cuttings), we can do range counting for queries that are the intersection of $p$ halfspaces, for $1 \le p \le d+1$, using a data structure of size $O(m)$, for $n \le m \le n^d$, in $O\left(\frac{n}{m^{1/d}}\log^{p-(d-p+1)/d} \left(\frac{m}{n}\right)\right)$ time. For $p=1$ this is $O(n/m^{1/d})$ time. However, Agarwal's survey on range searching (Table 36.3.2) claims the bound is $O\left(\frac{n}{m^{1/d}}\log(\frac{m}{n})\right)$. What is the correct statement of the bound? Alternatively, what am I misunderstanding? Finally, is there any hidden log term when $m=n^d$?

## 2 Answers

Matoušek's stronger time bound is correct.

The proof of Theorem 6.1 (in the journal version) uses an indirection trick that reduces the space bound required for logarithmic query time from $O(n^d)$ to $O(n^d/\operatorname{polylog} n)$. Intuitively, the trick is to cluster the points into subsets of polylogarithmic size, build a linear-space data structure for each subset, and then build a standard logarithmic-query-time structure over the subsets. Plugging the improved space bound into Matoušek's multi-level/tradeoff machinery—described in gory generality in the longer version of Agarwal's survey—gives Matoušek's form of the time-space tradeoff. (In fact, the indirection trick is just a very careful application of the standard tradeoff machinery.)

• Just to be explicit: Theorem 6.2 in Matousek's paper claims that halfspace counting can be done in $O(m)$ space, $O(n/m^{1/d})$ time. When $m = n^d$, this is $O(1)$ time... there is no unstated additive log factor? I only ask because in the survey Theorem 7 and Corollary 8 have an additive $O(log (m/n))$ that is not present in Matousek's statement of the theorem. – pkn Jan 25 '12 at 15:15
• Ah, I see. Yes, there's a bug; the upper bound $m \le n^d$ in the theorem statement is too loose. The proof requires $m = O(n^d / \log^{d-p+1} n)$; otherwise, the integer parameter $r$ would be less than $1$. Adding the logairthmic term to the query time also fixes the problem. – Jeffε Jan 25 '12 at 22:33

There is a brief discussion of results in half-space range searching just above Table 36.3.2 in Agarwal's Survey and another in section 4.3 of this survey. The former doesn't seem to give many details beyond "A space/query-time tradeoff for simplex range searching can be attained by combining the linear-size and logarithmic query-time data structures", but the latter seems to provide quite a bit more detail on the space / query-time tradeoff. I suggest looking at section 4.3, Theorem 7, Corollary 8, and their proofs. I haven't read them in enough detail to know if it fully answers your question, but it's at least a good place to start.