2010/12/16 Phil Endecott <spam_from_boost_dev@chezphil.org>:
My idea is to consider an interval (low,high) as a point in a 2D plain. Then, a query to find all of the intervals overlapping (a,b) is the same as the query to find all the points in the quarter-plane where low<b and high>a.
Any 2D data structure could be used to store these (e.g. quadtrees etc), but the aim here is to adapt a 1D data structure. I have used the Z-curve method [3] to do this efficiently for some years now and it works well. The idea is that you bitwise-interleave the two values and use this as the key. You can then iterate over all points in a rectangle by iterating over all points in the 1D range between the interleaved bottom left and top right corner values.
Hi Phil, I find your idea quite nifty and fascinating. The transformation from intervals to 2D plane to z-curve ordering is quite powerful and opens up new frames of thinking on the problem. I guess I need a little more thinking time and intend to post another answer tomorrow. Best regards, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de