Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

Question

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?

Answer 1

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. Discrete & Computational Geometry 47:711–730, 2012.

2. Bernard Chazelle. Lower bounds on the complexity of polytope range searching. Journal of the AMS 2(40):637–666, 1989.