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?