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.)
-
$\begingroup$ 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. $\endgroup$ – pkn Jan 25 '12 at 15:15
-
$\begingroup$ 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. $\endgroup$ – 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.
