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/ ---------
_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
