Chapter Notes

| < Day Day Up > |

## Chapter Notes

In their book, Preparata and Shamos [247] describe several of the interval trees that appear in the literature, citing work by H. Edelsbrunner (1980) and E. M. Mc-Creight (1981). The book details an interval tree for which, given a static database of n intervals, all k intervals that overlap a given query interval can be enumerated in O(k + lg n) time.

| < Day Day Up > |