Geometric Applications of BST

1-D Range Search

This is the extension for symbol table.

Insert key-value pair.
Search for key k.
Delete key k.
Range search: Find all keys between k1 & k2.
Range count: Number of keys between k1 & k2.

Implementation

Un Ordered List: Fast Insertion and slow search
Ordered List: Slow insert, binary search for k1 and k2 to do range search.

BST Implementation

Example1:

Java code to find the number of keys between low and high

// Running time is proportional to log(n)
public int size(key low, key high) {
    if(contains(high)){
        return rank(high) - rank(low) + 1;
    } else {
        return rank(high) - rank(low);
    }
}

Example 2:

Line Segment Intersection

Given N horizontal and vertical line segments, find all intersections.

Sweep-line algorithm

Sweep vertical line between left to right and record your observations

Algorithm:

x-coordinates define events.
h-segment (left endpoint): insert y-coordinate into BST.
h-segment (left endpoint): insert y-coordinate into BST.
v-segment: Range search for interval of y-end points.

Explanation:

Put x-coordinate in PQ (or Sort ) . -------------> N * log(N)
Insert y-coordinate into the BST . -------------> N * log(N)
Remove y-coordinate from the BST -------------> N * log(N)
Range Searches in BST -------------> N * log(N) + R

1D Interval Search Trees

Data structure to hold the set of overlapping intervals.

Create BST, where each node stores an interval (lo, hi).

Use left endpoint as BST key.
Store max endpoint in subtree rooted at node.

Algorithm

If interval in node intersects query interval, return it.
Else if left subtree is null, go right.
Else if max endpoint in left subtree is less than lo, go right.
Else go left.

Java Implementation

..............

 TreeNode x = root;
 
 while(x!=null){
     if(x.interval.insersects(lo,hi)){
         return x.interval;
     }else if(x.left == null) {
         x = x.right;
     }else if(x.left.max < lo){
         x = x.right;
     }else {
         x = x.left;
     }
 }

return null;

..............

Interval Search Tree Analysis

Implementation: Use a red-black BST ( easy to maintain auxiliary information using log N extra work per op ) to guarantee performance.

Orthogonal rectangle intersection

Goal: Find all intersections among a set of N orthogonal rectangles.

Here we use the same principle sweep line algorithm. Sweep one vertical line from left to right. when you encounter left end point insert y interval. and repeat the interval search until you get the right end point.

Algorithm

x-coordinates of left and right endpoints define events.
Maintain set of rectangles that intersect the sweep line in an interval search tree (using y-intervals of rectangle).
Left endpoint: Interval search for y-interval of rectangle; insert y-interval.
Right endpoint: Remove y-interval.