set representation question

[Johannes Waldmann]

John Meacham wrote:

> my intuition says something like binary trees annotated with the minimum
> and maximum value contained beneath each node so you may prune whole
> subtrees in constant time...

Yes. This may be one dimension too high,
but check out "segment trees" from Computational Geometry.
See Bentley, J.L., and D. Wood, An optimal algorithm for reporting 
intersections of rectangles, IEEE Trans. on Computers C-29 (1980), pp. 
571-577. http://citeseer.nj.nec.com/context/2049538/0

best regards
-- 
-- Johannes Waldmann,  Tel/Fax: (0341) 3076 6479 / 6480 --
------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------