<p>Matoušek's stronger time bound is correct.</p>

<p>The proof of Theorem 6.1 (<a href="http://www.springerlink.com/content/c867n18216603637/">in the journal version</a>) 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 <a href="http://www.cs.uiuc.edu/~jeffe/pubs/survey.html">the longer version of Agarwal's survey</a>—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.) </p>

CC BY-SA 3.0
2012-01-25T15:15:32.747Z
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
CC BY-SA 3.0
2012-01-25T22:33:40.447Z
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ε
CC BY-SA 3.0
2012-01-25T09:14:44.740Z
2012-01-25T09:14:44.740Z
Jeffε
<p>There is a brief discussion of results in half-space range searching just above Table 36.3.2 in <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8006" rel="nofollow">Agarwal's Survey</a> and another in section 4.3 of <a href="http://www.cs.uiuc.edu/~jeffe/pubs/pdf/survey-tr.pdf" rel="nofollow">this survey</a>. 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.</p>

CC BY-SA 3.0
2012-01-25T08:14:35.540Z
2012-01-25T08:20:42.363Z
2012-01-25T08:20:42.363Z
Joe
<p>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$?</p>

<reference-request><ds.data-structures><cg.comp-geom>
Tradeoff Bounds for Halfspace Range Counting
pkn
# Tradeoff Bounds for Halfspace Range Counting

(Asked by: username_0 on 2012-01-25)

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

**Tags:** reference-request, ds.data-structures, cg.comp-geom


---

## 2 answers

### Answer by username_1 on 2012-01-25. Score: 6 | Accepted answer

Matoušek's stronger time bound is correct.

The proof of Theorem 6.1 ([in the journal version](http://www.springerlink.com/content/c867n18216603637/)) 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](http://www.cs.uiuc.edu/~jeffe/pubs/survey.html)—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.)

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  

---

### Answer by username_2 on 2012-01-25. Score: 2

There is a brief discussion of results in half-space range searching just above Table 36.3.2 in [Agarwal's Survey](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8006) and another in section 4.3 of [this survey](http://www.cs.uiuc.edu/~jeffe/pubs/pdf/survey-tr.pdf). 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.


---

