1D Range Search

1) How many keys between lower bound and upper bound?

BST: rank(hi) - rank(low)

rank(hi): number of keys < hi

2) Find all keys between lo and hi

inorder:

1. Recursively find all keys in left subtree (if any could fall in range)
2. Check key in current node.
3. Recursively find all keys in right sub tree (if any could fall in range)

Line Segment Intersection

Non degeneracy assumption. All x- and y-coordinates are distinct.

Kd-Trees

Range search: find all keys that lie in a 2d range (points in a rectangle)

Range count: number of keys that lie in a 2d range (rectangle)

e.g. DB all people between 1 to 10,000 who's age is between 30-40

Nearest Neighbor

Interval Search Trees

Orthogonal Rectangle Intersection

Non degeneracy assumption. All x- and y-coordinates are distinct.

Interval tree with sweep-line