Boost logo

Boost :

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

>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
>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

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

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at