Lesson plan
Interval tree
In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree. The trivial solution to finding all overlapping intervals is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, output-sensitive algorithms, where the runtime is expressed in terms of m (the number of intervals produced by the query) may also be considered. Interval trees have a query time of O(\log n + m) and an initial creation time of O(n \log n) , while limiting memory consumption to O(n) . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(\log n) time.…
Article summary
In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree. The trivial solution to finding all overlapping intervals is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, output-sensitive algorithms, where the runtime is expressed in terms of m (the number of intervals produced by the query) may also be considered. Interval trees have a query time of O(\log n + m) and an initial creation time of O(n \log n) , while limiting memory consumption to O(n) . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(\log n) time.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.