I devised an algorithm that, given a set of points in a multidimensional space, can find all the points in an arbitrary box very efficiently.
My algorithm needs space O(n log^(d-1)n) and answers a query, in the worst case, in time O(log^(d-1)n), where d is the dimension of the space.
For instance, if the space is two-dimensional, it requires space O(nlogn) and answers a query, in the worst case, in time O(logn). As you can see, it's *very* fast, but requires some space.
I think it's an important result from a theoretic point of view and not only.
You can find my paper here:
Technical papers, as always, make algorithms look *much* more complex than they really are. If you want to discuss a part of the paper, you find an error, or there is a point particularly unclear, don't hesitate to ask.