7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jeffε Jul 8 '13 at 16:59
  • 1
    $\begingroup$ 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. $\endgroup$ – ymbirtt Jul 8 '13 at 18:02
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ymbirtt Jul 9 '13 at 11:35
  • $\begingroup$ Yes, that's right! $\endgroup$ – Jeffε Jul 10 '13 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.