<h2>No.</h2>

<p>Rotated-box queries and simplex queries are both generalizations of <strong>slab</strong> queries, where a slab is the volume between two parallel hyperplanes.  Most lower bound proofs for simplex range searching actually assume that all query simplices are slabs of constant thickness.  In particular, Chazelle [2] proved the following theorem.</p>

<blockquote>
  <p>Let $P$ be a random set of $n$ points, generated independently and uniformly in the unit hypercube $[0,1]^d$.  With probability at least $1/2$, any data structure of size $s$ that answers queries in $P$ for slabs of width $1/24$ in time $t$ in the semigroup arithmetic model must satisfy the inequality $st^d = \Omega((n/\log n)^d)$, or $st^2 = \Omega(n^2)$ when $d=2$.</p>
</blockquote>

<p>The constants $1/2$ and $1/24$ are not particularly important here; different choices merely change the constant hidden in the $\Omega(\,)$ notation.  Thus, if you are allowed only linear space, your query time must be $\Omega(n^{1-1/d} / \operatorname{polylog} n)$; on the other hand, if you require polylogarithmic query time, you must use $\Omega(n^d / \operatorname{polylog} n)$ space.</p>

<p>More recently, Arya, Mount, and Xia [2] proved nearly identical lower bounds (under some reasonable assumptions about the underlying semigroup) for the even simpler case of <strong>halfspace</strong> queries, where a halfspace consists of all points on one side of a single halfplane.</p>

<p><strong>tl;dr: Don't rotate your boxes.</strong></p>

<hr>

<ol>
<li><p>Sunil Arya, David M. Mount, and Jian Xia.  <a href="http://www.cs.umd.edu/~mount/Papers/dcg12-lower-bound.pdf" rel="nofollow">Tight lower bounds for halfspace range searching</a>.  <em>Discrete &amp; Computational Geometry</em> 47:711–730, 2012.</p></li>
<li><p>Bernard Chazelle.  <a href="http://www.cs.princeton.edu/~chazelle/pubs/LBpolytopeRangeSearch.pdf" rel="nofollow">Lower bounds on the complexity of polytope range searching</a>.  <em>Journal of the AMS</em> 2(40):637–666, 1989.</p></li>
</ol>

CC BY-SA 3.0
2013-07-09T11:35:55.947Z
Nice one. Would it also be correct to conclude that we can't do this sort of query over an arbitrary d-dimensional ball or an arbitrary torus, since we can approximate a halfspace with the set of points inside a really big ball a really long way away from our points?
ymbirtt
CC BY-SA 3.0
2013-07-10T00:02:23.663Z
Yes, that's right!
Jeffε
CC BY-SA 3.0
2013-07-08T18:24:23.167Z
2013-07-10T00:03:22.480Z
2013-07-10T00:03:22.480Z
Jeffε
<p>Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear initialisation using roughly linear storage, I would like to know the total mass of all the points that fall within various queried subspaces in polylogarithmic time.</p>

<p>If our queries are all axis-parallel boxes, ie sets of points defined by a cartesian product of intervals on each axis, we can apply some standard, easily-googleable range searching methods and achieve this without too much difficulty.</p>

<p>If our queries are all simplices, there are currently no known methods which satisfy both these criteria, either we use polynomial space and initialisation to achieve a polylog query time, or we use roughly linear space and have sublinear, but not logarithmic, query times.</p>

<p>What if our queries are all boxes, but each is rotated in some way? We can define such a box in a few ways, but for the sake of concreteness suppose I will give you a sequence of sets of hyperplanes, each with exactly one parallel partner, intersecting all others orthogonally, defining some boxey subspace between them. Is there a way of solving this slightly simpler problem with roughly linear initialisation and storage but polylogarithmic queries? Alternatively, if I were to give you a method of doing this, would you be able to use it to solve the simplex case of this problem in a similarly easy way?</p>

CC BY-SA 3.0
2013-07-08T16:59:17.190Z
_but each is rotated in some way?_ — Do you mean "but each is rotated **the same** way"?  If so, just rotate the coordinate system to match before preprocessing the points.
Jeffε
CC BY-SA 3.0
2013-07-08T18:02:32.063Z
I mean each is rotated in some way, as in some arbitrary way that may differ between queries. The problem would, as you rightly said, be trivial if all boxes had the same orientation.
ymbirtt
<ds.algorithms><ds.data-structures><cg.comp-geom>
Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?
ymbirtt
# Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

(Asked by: username_0 on 2013-07-08)

Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear initialisation using roughly linear storage, I would like to know the total mass of all the points that fall within various queried subspaces in polylogarithmic time.

If our queries are all axis-parallel boxes, ie sets of points defined by a cartesian product of intervals on each axis, we can apply some standard, easily-googleable range searching methods and achieve this without too much difficulty.

If our queries are all simplices, there are currently no known methods which satisfy both these criteria, either we use polynomial space and initialisation to achieve a polylog query time, or we use roughly linear space and have sublinear, but not logarithmic, query times.

What if our queries are all boxes, but each is rotated in some way? We can define such a box in a few ways, but for the sake of concreteness suppose I will give you a sequence of sets of hyperplanes, each with exactly one parallel partner, intersecting all others orthogonally, defining some boxey subspace between them. Is there a way of solving this slightly simpler problem with roughly linear initialisation and storage but polylogarithmic queries? Alternatively, if I were to give you a method of doing this, would you be able to use it to solve the simplex case of this problem in a similarly easy way?

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

> **Comments:**
> **username_1**: _but each is rotated in some way?_ — Do you mean "but each is rotated **the same** way"?  If so, just rotate the coordinate system to match before preprocessing the points.  
> **username_0**: I mean each is rotated in some way, as in some arbitrary way that may differ between queries. The problem would, as you rightly said, be trivial if all boxes had the same orientation.  

---

## 1 answers

### Answer by username_1 on 2013-07-08. Score: 8 | Accepted answer

## No.

Rotated-box queries and simplex queries are both generalizations of **slab** queries, where a slab is the volume between two parallel hyperplanes. Most lower bound proofs for simplex range searching actually assume that all query simplices are slabs of constant thickness. In particular, Chazelle [2] proved the following theorem.

> Let $P$ be a random set of $n$ points, generated independently and uniformly in the unit hypercube $[0,1]^d$. With probability at least $1/2$, any data structure of size $s$ that answers queries in $P$ for slabs of width $1/24$ in time $t$ in the semigroup arithmetic model must satisfy the inequality $st^d = \Omega((n/\log n)^d)$, or $st^2 = \Omega(n^2)$ when $d=2$.

The constants $1/2$ and $1/24$ are not particularly important here; different choices merely change the constant hidden in the $\Omega(\,)$ notation. Thus, if you are allowed only linear space, your query time must be $\Omega(n^{1-1/d} / \operatorname{polylog} n)$; on the other hand, if you require polylogarithmic query time, you must use $\Omega(n^d / \operatorname{polylog} n)$ space.

More recently, Arya, Mount, and Xia [2] proved nearly identical lower bounds (under some reasonable assumptions about the underlying semigroup) for the even simpler case of **halfspace** queries, where a halfspace consists of all points on one side of a single halfplane.

**tl;dr: Don't rotate your boxes.**

---

1. Sunil Arya, David M. Mount, and Jian Xia. [Tight lower bounds for halfspace range searching](http://www.cs.umd.edu/~mount/Papers/dcg12-lower-bound.pdf). *Discrete & Computational Geometry* 47:711–730, 2012.
2. Bernard Chazelle. [Lower bounds on the complexity of polytope range searching](http://www.cs.princeton.edu/~chazelle/pubs/LBpolytopeRangeSearch.pdf). *Journal of the AMS* 2(40):637–666, 1989.

> **Comments:**
> **username_0**: Nice one. Would it also be correct to conclude that we can't do this sort of query over an arbitrary d-dimensional ball or an arbitrary torus, since we can approximate a halfspace with the set of points inside a really big ball a really long way away from our points?  
> **username_1**: Yes, that's right!  

---

