# 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`.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-0e937e1c5aa49a3155eb2b70e9a26aa4418c8031%2Fimage%20\(88\).png?alt=media)

**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:**

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-cb2b237628faf4d4456e08880ec13cdbfadb4627%2Fimage%20\(89\).png?alt=media)

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

```java
// 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:**

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-89d46b80fee1a2b1de7ad55a10b1c7fe02410518%2Fimage%20\(90\).png?alt=media)

## Line Segment Intersection

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

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-d7d90e714e9e95cd7e1b53fa8751d20ed34cb0df%2Fimage%20\(83\).png?alt=media)

### 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.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-414e2b147a699db6f62a167992025dd1c7301c4c%2Fimage%20\(92\).png?alt=media)

### 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.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-420ff862ef13cefe51ba360bb9f20f10519d2215%2Fimage%20\(86\).png?alt=media)

### Java Implementation

```java
..............

 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.

![order of growth of running time for N intervals](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-c07b0ddf0323c53a5babe07b8113dcf972545f88%2Fimage%20\(85\).png?alt=media)

## Orthogonal rectangle intersection

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

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-460a91c90d0a79452fbbfa00e6cb9590697d7470%2Fimage%20\(87\).png?alt=media)

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.

![Orthogonal Rectangle Intersection](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-83bd8b388935e673db6e4791db77b344cecf7a5e%2Fimage%20\(84\).png?alt=media)

**Analysis**

* Put x-coordinate in PQ (or Sort ) . -------------> `N * log(N)`
* Insert y-coordinate into the BST . -------------> `N * log(N)`
* Reomve y-coordinate from the BST -------------> `N * log(N)`
* Interval Search for y Coordinates -------------> `N * log(N) + R * log(N)`

## Summary

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-0b1ffc9ee4553b43a535ac5ddbea8f5d967f00ea%2Fimage%20\(91\).png?alt=media)