Range searching is probably the most well explored area in computational geometry, and one that has led to the richest array of techniques, both for upper bounds and lower bounds.
The problem itself is very easy to state. You're given points in a range, and a query from a family of ranges. Find all points contained in the range, and report the set of points (searching), the cardinality of points (counting) or even whether the range is non-empty (emptiness).
If one defines an appropriate commutative semigroup, then all of the above formulations can be captured by the same basic problem. Given a mapping w from points to the semigroup, compute the sum (with respect to the semigroup) of w(p) for all points in the range. Searching maps to the union operation, counting to addition, and emptiness to the OR function.
Most results in range searching are phrased in terms of space-time tradeoffs: if you are willing to pay m space, what is the query time as a function of m and n, the number of points ? The interesting points are at the extremes: If you want logarithmic query time (this ignores the time to output the search results, or you can consider counting queries), then you need polynomial space, and if you want linear space, then you'll end up with near-linear query time.
A flurry of results starting in the late 80s and culminating in the early 90s resolved most of the open problems in range searching, especially for the challenging simplex (or halfspace) range searching problems. The survey by Agarwal and Erickson has more details.
For all intents and purposes, this area appeared be to a closed one. More recently, there was work on tradeoffs for approximate range searching (when you might allow points that are "near" the range to be included in the answer). Here, it was possible to transfer the high complexity from terms involving n (or d) to terms involving epsilon, the error parameter (again, I oversimplify; see here and here for more details).
Recently though, two papers by Arya, Malamatos and Mount appear to have opened up some new angles (pun intended) to range searching. The first paper (which appeared in STOC this year) is titled, in Wildesque fashion, 'On the Importance of Idempotence".
The premise is neat: in all the upper and lower bounds for range searching, the group structure is not explored in any particular way (for technical reasons, the group must be a "faithful semigroup", but that's it). What they show in their paper is that for exact range searching to a degree, and more importantly for approximate range searching, the group structure can change the bounds. Specifically, if the group operation is idempotent, i.e a + a = a, then the (matching) upper and lower bounds for approximate range searching reduce to the square root of their previous values (i.e by a factor of 2 in the exponent). Idempotent group operators include min (used to find the smallest element in a range) and OR (to check range emptiness).
[Aside]
What's really interesting about this is that idempotence itself can be viewed as a limit of a "dequantization process" over integral domains. One example of this is how the field (R, max,+) can be retrieved from the field (R, +, *) (there are some technical details needed) by using the mapping x -> 1/h ln(x), as h tends to infinity. The question is then: can the difference between the idempotent and integral bounds on range searching be viewed as two points on a continuum parameterized by such a parameter ?
There's a lot of work out there on idempotence, so-called "tropical mathematics", and the relation between quantum and classical phenomena. All very interesting stuff.
[End Aside]
In a paper coming up at SoCG, Arya, Malamatos and Mount go one step further. They further show that the shape of the ranges is also very important. Their earlier results on idempotence were for ball queries: in this paper they show that if the queries are angular (like rectangles), then the separation between idempotent and integral semigroups doesn't quite show up, and that smooth, well rounded queries (like balls) are needed for this to work.
This idempotence stuff is intersting. Is it easy to prove that there is no group such that it's binary operator is idempotent?
ReplyDeletePosted by Anonymous