View Full Document

# Geometric Algorithms

View Full Document
View Full Document

3 views

Unformatted text preview:

Geometric Algorithms range search quad and kd trees intersection search VLSI rules check References Algorithms in C 2nd edition Chapters 26 27 http www cs princeton edu introalgsds 73range http www cs princeton edu introalgsds 74intersection 1 Overview Types of data Points lines planes polygons circles This lecture Sets of N objects Geometric problems extend to higher dimensions Good algorithms also extend to higher dimensions Curse of dimensionality Basic problems Range searching Nearest neighbor Finding intersections of geometric objects 2 range search quad and kd trees intersection search VLSI rules check 3 1D Range Search Extension to symbol table ADT with comparable keys Insert key value pair Search for key k How many records have keys between k1 and k2 Iterate over all records with keys between k 1 and k2 Application database queries Geometric intuition Keys are point on a line How many points in a given interval insert B B insert D BD insert A ABD insert I ABDI insert H ABDHI insert F ABDFHI insert P ABDFHIP count G to K 2 search G to K H I 4 1D Range search implementations Range search How many records have keys between k1 and k2 Ordered array Slow insert binary search for k1 and k2 to find range Hash table No reasonable algorithm key order lost in hash BST In each node x maintain number of nodes in tree rooted at x Search for smallest element k1 and largest element k2 insert count range ordered array N log N R log N hash table 1 N N BST log N log N R log N N records R records that match nodes examined within interval not touched 5 2D Orthogonal Range Search Extension to symbol table ADT with 2D keys Insert a 2D key Search for a 2D key Range search find all keys that lie in a 2D range Range count how many keys lie in a 2D range Applications networking circuit design databases Geometric interpretation Keys are point in the plane Find all points in a given h v rectangle 6 2D Orthogonal range Search Grid implementation Grid implementation Sedgewick 3 18 Divide

Unlocking...