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