Princeton Alogorithm COS226 Week

Overview

this lecture is the most interesting lecture in the part i, because it taught data structure and algorithm, many other place not cover.
in this lecture, we will learn 1d range search,

image.png

1d range search

in ordered symbol table, we need to add two more operation

1. range search : find all keys between k1 and k2
2. range count: find number of keys between k1 and k2.

in geometric interpretation, the problem is like keys are point on a line, we need to find/count points in a given 1d interval

image.png

if we use balanced binary search tree, we can use rank to solve the range count problem

image.png
image.png

added extra credit for this implementation in my github

line segment intersection

image.png
added extra credit for this implementation in my github

KD Tree

how about 2-d orthogonal range search?
now we need to extend ordered symbol-table to 2d keys
insert 2d key, search for 2d key, range search and range count

we can solve this problem by grid

image.png image.png

but when points are clustering, the problem will exists.

image.png

now we can use 2d tree to solve problem.

image.png
image.png
image.png

to find all points in a query axis-aligned rectangle

the basic plan is
check if point in node lies in given rectangle
if any in, then recursively search left/ bottom
if any in, recursively search right/ top

assuming tree is balanced, typical case to range search is R + logN, the worst case is R + SQRT(N)

nearest neighbor search in a 2d tree demo

check distance from point in node to query point
recursively search left/ bottom (if it could contain a closer point)
recursively search right/ top(if it could contain a closer point)
organize method so that it begins by searching for query point

image.png
poject cover this implementation

interval search tree

image.png

interval search tree is like a BST, but in each node we save an interval (lo, hi)
use left end point as BST key.
and we need store additional field which called max endpoint in subtree rooted at node.

image.png

insert

insert （lo, hi） into BST, using lo as the key
update max in each node on search path

search tree

to search for any one interval that intersect query interval
if interval in node intersects query interval, return it
else if left subtree is null, go right
else if max end point in left subtree is less than lo, go right
else go left

image.png

Case 1. if search goes right, then no intersection in left.

Case 2. if search goes left, then there is either an intersection in left subtree or no intersections in either.

image.png
added extra credit for this implementation in my github

Orthogonal rectangle intersection

image.png image.png

added extra credit for this implementation in my github

Project KD-TREE

image.png image.png

first implement kd-tree node, we use left, right pointer to is children and in node, will save it is vertical or horizontal, and save it is back rectangle
the root back rectangle is (0,0,1,1)

then we could implement insert, it just compare the node should be left subtree or right subtree, when compare we need diff vertical and horizontal use x or y to compare.

after build the kd-tree
we can implement the nearest and range

range

1. add node.point in result if it is in query rectangle
2. the diving line in kd-tree is intersect the query rectangle
3. if yes, search both node
4. if no, go the child which is closer to query rectangle

nearest

1. if cur point is nearest than the curerent nearest ,update it.
2. compare the node should be left subtree or right subtree
3. search that tree
4. check other tree when the target node distanceto the other node's background rectangle is smaller than the current min distance.

bonus

we can calculate recthv in recursive function of range search and nearest.
so we can discard recthv in node to save memory

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226