Re: [boost] Re: new component, extent_set<>

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-12-31 16:48:12

At 10:07 AM 12/31/2001, David Abrahams wrote:

 >A data structure I've needed (and used) from time to time which I presume 

 >is
 >different from everything described so far in this thread is an "interval
 >tree". An interval tree is an RB-tree of intervals sorted on the start
 >position of each interval, where each node contains an additional record 
of
 >the maximum end position of all intervals in the subtree rooted at that
 >node. The intervals are allowed to overlap. It is possible to efficiently
 >enumerate all intervals in the tree that overlap any given interval, for
 >example.

That sounds like a one-dimensional case of the general n-dimensional R-tree 
(or R*tree or R+tree refinements) used for spatial search.  Although I've 
never used anything other than a B-tree, I'm pretty sure you can implement 
an R-/*/+tree on top of any kind of binary or multi-way underlying tree 
structure.

By the way, an ordering other than on start position can have dramatically 
better performance (at least for multi-dimensional cases).

See the book Spatial Databases by Rigaux, Scholl, and Voisard, beginning 
around page 238.  ISBN 1-55860-588-6.

--Beman