[Algorithms I] Week 5-2 Geometric Applications of BSTs

1. 1d Range Search

Goal: intersections of geometric objects.

Solution: BST

operations required:

  • insert
  • search
  • delete
  • range search: all keys between k1 and k2
  • range count: how many keys are between k1 and k2

→ find points on an interval

implementation by BST

range count
using the rank() function for the BST (or use the size of a tree)


public int size(Key hi, Key lo){   
    if(contains(hi)) return rank(hi)-rank(lo)+1;   
    else return rank(hi) - rank(lo);   

range search
类似inorder traversal的方式:

  • find in left subtree (if could fall into range)
  • check current node
  • find in right subtree

running time: R+lgN (R=nb of nodes in range)

2. Line Segment Intersection

Orthognal line segment intersection search:
find all intersections given N horizontal/vertical lines

Non-degeneracy assumption: all x-coord and y-coord are distinct.

naive algo: check all pairs...

Sweep-line algorithm

  • sweep a vertical line from left to right.
    • when hit the left end of horizontal-segment (h-seg) → insert into a BST
    • when hit the right end of a h-seg → delete from BST
    • when hit a vertical-seg: ⇒ 1d range search !

没有仔细讲, 不过我觉得就是把所有的x坐标排好序, 有个skyline问题也是涉及如何sweep的.

running time is NlgN+R (R=nb of intersections).

  • Sort by x-coord (or use PQ) → NlgN
  • insert/delete y-coord to BST → NlgN
  • range search → NlgN + R

3. Kd-trees

An extension of BST: 2d-keys.

  • insert: insert 2d points
  • search
  • range search: find all keys lying in a 2d rectangle (h-v rectangle)
  • range count

gird implementation

divide space into a M-by-M grid (uniform squares).
space: N + M^2
time: 1 + N/M^2
→ choose square to balance space and time.
problem: points are not uniformly distributed.

2d tree

Use a tree to represent the subdivision of the space.

2d tree: recursively divide the space into 2 halfplanes

construct the 2d tree by adding points: alternating between horizontal and vertical partitioning for each level of tree.

Data structure: BST alternating x and y-coords as key.

Range search for 2d tree

find all points lying in a rectangle.
依然类似tree traversal算法:

  • check point in node
  • find in left subtree (if could be in range — the rectangle intersects the splitting line)
  • find in right subtree

Typical case: R + lgN
worst case: R+ sqrt(N) (even if tree is balanced)
(proof is hard)

Nearest Neighbour seach

find closest point to a query point.

  • check dist from query point to node
  • check in left tree (if could contain a closer point — 和两点连线与splitting line的角度有关系)
  • check in right tree

typical case: lgN
worst case: N

Flocking boids
3 simple rules to get a simulation of flocking.

Kd tree

partition the k-dim space into 2 halfspaces.
cycle through k dimensions.


Nbody simulation:
treat clusters as an aggregated node

4. Interval search tree

1d interval search: data are intervals

  • insert interval
  • search interval
  • delete interval
  • intersection query: find all intervals that intersects (lo,hi)

Nondegeneracy assumption: all left endpoint of intervals are distinct.


put(Key lo, Key hi, Value val)   
get(Key lo, Key hi)   
delete(Key lo, Key hi)   
Iterable<Key> intersects(Key lo, Key hi)

Interval search tree:

  • BST using left endpoint as key
  • in each node: store the max right endpoint of the subtree

类似BST, 加上维护一下maxendpoint即可.

search any one interval that intersects (lo,hi)

  • if node intersects, return
  • if left.maxendpoint < lo: go right
  • else: go left

*proof. *
主要证明一点: if no intersection to left ⇒ then no intersection to the right

5. Rectangle intersection

Goal: find all intersection among N rectangles.
(non degeneracy assumption: all x and y are distinct)

bottom line: linearithmic algo.

sweep-line algorithm:
sweep vertical line from left to right.

  • when hit left part of a rect ⇒ put into an interval search tree
  • when hit right part of a rect ⇒ remove interval
  • every time befor adding ⇒ check intersection

reduces the 2d rect intersection pb to 1d interval search pb.



comments powered by Disqus