A data structure for finding all intervals that overlap a point
Yu Chen · 2002
Highspeed finding of the collection of all intervals overlapping a point is one of the urgent problems to be solved in the applications of computer graphology and mode matching. This paper introduces a data structure to find all intervals overlapping a pointthe interval skip list.The function and property of this data structure is similar to that of AVL Tree. ( AVL Tree is a kind of balanced tree with two branches. The property of the tree is that the height difference between the left branch and the right one at any point is not more than 1. It's quite efficient to inquire and retrieve by this tree structure.) With regard to execution , however, it's much easier than that of AVL Tree because it can find the collection of all intervals overlapping a point in high speed. Searching an ISlist containing n intervals to find intervals overlapping a point takes expected time O(logn+L) where L is the number of matching intervals. Inserting or deleting an interval takes expected time O(log2n).1fig.,5refs.