1d Range Search

• To find a range search which is log n for insert, range count and range search
  • Use BST to recursively check left subtree and right subtree

interval search tree

A BST, where each node stores an interval

• use left endpoint as BST key
• store the max endpoint in subtree rooted at node

Line Segment Intersection - Sweep Line

1. Put all the x in the PQ
2. Scan, insert left endpoint to the into BST
3. remove the right endpoint from the BST
4. If it is a vertical line, do the range search in BST

2d Range Search

Create a BST tree, but instead of storing the key, it stores the point. It alternate using x and y coordinates as key

• each level of BST is the vertical or horizontal alternatively
• left subtree is the left or down point relative to the parent point
• right subtree is the right or up point relative to the parent point

Example:

• To find points contained in a rectangle
  • check if point in nodes lies in given rectangle
  • recursively search left/bottom
  • recursively search right/top
  • R + log N
• Find closet point to query point
  • check distance from point in node to query point
  • recursively search left/bottom
  • recursively search right/top
  • log N

2d orthogonal rectangle intersection search

• put x-coordinates on a PQ
• insert y-intervals into ST
• delete y-interval from ST
• interval searches for y-intervals