Subject: [boost] Interval Trees & ICL
From: Bruce Adams (tortoise_74_at_[hidden])
Date: 2010-12-14 13:26:22
I have been working on a problem for which a suitable solution is an
efficient container of intervals.
The two main candidates would be something like to boost::split_interval_set or
a centred interval tree
(along the lines of http://en.wikipedia.org/wiki/Interval_tree).
It seems to me that the characteristics of an interval tree differ sufficiently
from the containers defined in ICL that they might make a useful addition.
For the case where there is a potentially large number of overlapping intervals
a split_interval_set will be less efficient
than an interval tree. In the worst case intervals would be split down to unit
Searching the archives I see there was some discussion of interval trees in the
context of ICL but the additional of an interval tree
container did not, as far as I can tell, come up (perhaps because it should
first appear in a boost release before there is any consideration
of adding to it?). I have a few questions:
1. Is there a specific name for the data structures provided by the ICL?
I have searched the literature and cannot find any mention of sets that split or
combine intervals this way.
It is either a genuinely novel concept, which I find difficult to believe, or I
haven't used the correct search terms (interval, extent or segment).
Either way, I would like to update wikipedia appropriately to help other lost
2. Are there any compelling reasons why interval trees are less useful than the
containers provided by the ICL?
3. Perhaps based on the answer to 2. Would interval trees be a sensible addition
to the ICL?
4. Are there any other classes of interval container worthy of mention?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk